×

zbMATH — the first resource for mathematics

Universal completability, least eigenvalue frameworks, and vector colorings. (English) Zbl 1371.05162
Summary: An embedding \(i \mapsto p_i\in \mathbb {R}^d\) of the vertices of a graph \(G\) is called universally completable if the following holds: For any other embedding \(i\mapsto q_i \in \mathbb {R}^{k}\) satisfying \(q_i^{T}q_j = p_i^{T}p_j\) for \(i = j\) and \(i\) adjacent to \(j\), there exists an isometry mapping \(q_i\) to \(p_i\) for all \( i\in V(G)\). The notion of universal completability was introduced recently due to its relevance to the positive semidefinite matrix completion problem. In this work we focus on graph embeddings constructed using the eigenvectors of the least eigenvalue of the adjacency matrix of \(G\), which we call least eigenvalue frameworks. We identify two necessary and sufficient conditions for such frameworks to be universally completable. Our conditions also allow us to give algorithms for determining whether a least eigenvalue framework is universally completable. Furthermore, our computations for Cayley graphs on \(\mathbb {Z}_2^n\) \((n \leq 5)\) show that almost all of these graphs have universally completable least eigenvalue frameworks.
In the second part of this work we study uniquely vector colorable (UVC) graphs, i.e., graphs for which the semidefinite program corresponding to the Lovász theta number (of the complementary graph) admits a unique optimal solution. We identify a sufficient condition for showing that a graph is UVC based on the universal completability of an associated framework. This allows us to prove that Kneser and \(q\)-Kneser graphs are UVC. Lastly, we show that least eigenvalue frameworks of 1-walk-regular graphs always provide optimal vector colorings and furthermore, we are able to characterize all optimal vector colorings of such graphs. In particular, we give a necessary and sufficient condition for a 1-walk-regular graph to be uniquely vector colorable.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C62 Graph representations (geometric and intersection representations, etc.)
05C15 Coloring of graphs and hypergraphs
Software:
SageMath
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N; Kahale, N, A spectral technique for coloring random 3-colorable graphs, SIAM J. Comput., 26, 1733-1748, (1997) · Zbl 0884.05042
[2] Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Universitext. Springer, New York (2012) · Zbl 1231.05001
[3] Cameron, PJ; Goethals, J-M; Seidel, JJ; Shult, EE, Line graphs, root systems, and elliptic geometry, J. Algebra, 43, 305-327, (1976) · Zbl 0337.05142
[4] Colin de Verdiére, Y, Sur un nouvel invariant des graphes et un critère de planarité, J. Comb. Theory Ser. B, 50, 11-21, (1990) · Zbl 0742.05061
[5] Connelly, R.: Stress and Stability. http://www.math.cornell.edu/ connelly/Tensegrity.Chapter.2.ps (2001)
[6] Duffus, D; Sands, B; Woodrow, RE, On the chromatic number of the product of graphs, J. Graph Theory, 9, 487-495, (1985) · Zbl 0664.05019
[7] Fiedler, M, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J., 25, 619-633, (1975) · Zbl 0437.15004
[8] Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall Mathematics Series. Chapman & Hall, New York (1993)
[9] Godsil, CD, Eigenpolytopes of distance regular graphs, Can. J. Math., 50, 739-755, (1998) · Zbl 0955.05115
[10] Godsil, CD; Newman, MW, Independent sets in association schemes, Combinatorica, 26, 431-443, (2006) · Zbl 1121.05085
[11] Godsil, C; Roberson, DE; Rooney, B; Šámal, R; Varvitsiotis, A, Graph cores via universal completability, Electron. Notes Discrete Math., 49, 337-344, (2015) · Zbl 1346.05195
[12] Godsil, C., Roberson, D.E., Rooney, B., Šámal, R., Varvitsiotis, A.: Graph homomorphisms via vector colorings. arXiv:1610.10002 (2016) · Zbl 1346.05195
[13] Godsil, C.D., Roberson, D.E., Rooney, B., Šámal, R., Varvitsiotis, A.: Vector colorings of categorical products (in preparation) · Zbl 1371.05162
[14] Godsil, C; Roberson, DE; Šámal, R; Severini, S, Sabidussi versus hedetniemi for three variations of the chromatic number, Combinatorica, 36, 395-415, (2015) · Zbl 1389.05040
[15] Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001) · Zbl 0968.05002
[16] Javanmard, A; Montanari, A; Ricci-Tersenghi, F, Phase transitions in semidefinite relaxations, Proc. Natl. Acad. Sci. USA, 113, e2218-e2223, (2016) · Zbl 1359.62188
[17] Kannan, R., Vempala, S.: Spectral Algorithms. Foundations and Trends in Theoretical Computer Science, vol. 4(3-4). Now, Boston (2009)
[18] Karger, D; Motwani, R; Sudan, M, Approximate graph coloring by semidefinite programming, J. ACM, 45, 246-265, (1998) · Zbl 0904.68116
[19] Laurent, M; Varvitsiotis, A, Positive semidefinite matrix completion, universal rigidity and the strong Arnold property, Linear Algebra Appl., 452, 292-317, (2014) · Zbl 1291.90165
[20] Laurent, M; Varvitsiotis, A, A new graph parameter related to bounded rank positive semidefinite matrix completions, Math. Program. Ser. A, 145, 291-325, (2014) · Zbl 1293.05238
[21] Lovász, L; Schrijver, A, On the null space of a Colin de Verdière matrix, Ann. Inst. Fourier (Grenoble), 49, 1017-1026, (1999) · Zbl 0923.05038
[22] Pak, I; Vilenchik, D, Constructing uniquely realizable graphs, Discrete Comput. Geom., 50, 1051-1071, (2013) · Zbl 1280.05092
[23] Schrijver, A, A comparison of the delsarte and lovász bounds, IEEE Trans. Inform. Theory, 25, 425-429, (1979) · Zbl 0444.94009
[24] The Sage Developers: Sage Mathematics Software (Version 6.9). http://www.sagemath.org (2015) · Zbl 0955.05115
[25] Varvitsiotis, A.: Combinatorial conditions for low rank solutions in semidefinite programming. PhD Thesis, Tilburg University, Tilburg. https://pure.uvt.nl/ws/files/1551485/final_version_thesis.pdf (2013) · Zbl 1293.05238
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.