In this paper we study the existence of homomorphisms @math using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number @math for which there exists an assignment of unit vectors @math to its vertices such that @math when @math . Our approach allows to reprove, without using the Erdős-Ko-Rado Theorem, that for @math the Kneser graph @math and the @math -Kneser graph @math are cores, and furthermore, that for @math there exists a homomorphism @math if and only if @math divides @math . In terms of new applications, we show that the even-weight component of the distance @math -graph of the @math -cube @math is a core and also, that non-bipartite Taylor graphs are cores. Additionally, we give a necessary and sufficient condition for the existence of homomorphisms @math when @math . Lastly, we show that if a 2-walk-regular graph (which is non-bipartite and not complete multipartite) has a unique optimal vector coloring, it is a core. Based on this sufficient condition we conducted a computational study on Ted Spence's list of strongly regular graphs and found that at least 84 are cores.
@cite_0: In the Graph Realization Problem (GRP), one is given a graph (G ), a set of non-negative edge-weights, and an integer (d ). The goal is to find, if possible, a realization of (G ) in the Euclidian space ( R ^d ), such that the distance between any two vertices is the assigned edge weight. The problem has many applications in mathematics and computer science, but is NP-hard when the dimension (d ) is fixed. Characterizing tractable instances of GRP is a classical problem, first studied by Menger in 1931. We construct two new infinite families of GRP instances which can be solved in polynomial time. Both constructions are based on the blow-up of fixed small graphs with large expanders. Our main tool is the Connelly’s condition in Rigidity Theory, combined with an explicit construction and algebraic calculations of the rigidity (stress) matrix. As an application of our results, we describe a general framework to construct uniquely k-colorable graphs. These graphs have the extra property of being uniquely vector k-colorable. We give a deterministic explicit construction of such a family using Cayley expander graphs.
@cite_20: This paper addresses the following three topics: positive semidenite (psd) matrix completions, universal rigidity of frameworks, and the Strong Arnold Property (SAP). We show some strong connections among these topics, using semidenite programming as unifying theme. Our main contribution is a sufcient condition for constructing partial psd matrices which admit a unique completion to a full psd matrix. Such partial matrices are an essential tool in the study of the Gram dimension gd(G) of a graph G, a recently studied graph parameter related to the low psd matrix completion problem. Additionally, we derive an elementary proof of Connelly’s sucient condition for universal rigidity of tensegrity frameworks and we investigate the links between these two sucient conditions. We also give a geometric characterization of psd matrices satisfying the Strong Arnold Property in terms of nondegeneracy of an associated semidenite program, which we use to establish some links between the Gram dimension gd( ) and the Colin de Verdi ere type graph parameter = ( ).
In order for our approach to work, we must be able to identify UVC graphs and, moreover, find their unique vector colorings. This is the problem we consider in the first part of this work. UVC graphs are interesting in their own right. They were first introduced in @cite_0 to construct tractable instances of the graph realization problem. In the same work UVC graphs were used to construct uniquely colorable graphs. UVC graphs are also closely related to the notion of universal completability (equivalently, the universal rigidity of apex graphs). This in turn is relevant to the low-rank matrix completion problem @cite_20 .