Invariant of Colin de Verdier

Invariant of Colin de Verdier - characteristic of the graph $\mu (G)$ ${\ displaystyle \ mu (G)}$ $\ mu (G)$ defined for any graph G , introduced by Yves Kolen de Verdier in 1990 in the process of studying the multiplicity second eigenvalue of some Schrödinger operators . ^[one]

Content

Definition

Let be $G=(V,E)$ ${\ displaystyle G = (V, E)}$ Is a simple (not containing loops and multiple edges) acyclic graph. Without loss of generality, we name the set of vertices as follows: $V=\{1,\dots ,n\}$ ${\ displaystyle V = \ {1, \ dots, n \}}$ . Then $\mu (G)$ ${\ displaystyle \ mu (G)}$ Is the largest corank of any such matrix $M=(M_{i,j})\in \mathbb {R} ^{(n)}$ ${\ displaystyle M = (M_ {i, j}) \ in \ mathbb {R} ^ {(n)}}$ , what:

(M1) for any $i, j$ ${\ displaystyle i, j}$ where $i\neq j$ ${\ displaystyle i \ neq j}$ : $M_{i,j}<0$ ${\ displaystyle M_ {i, j} <0}$ if i and j are adjacent, and $M_{i,j}=0$ ${\ displaystyle M_ {i, j} = 0}$ , otherwise
(M2) M has exactly one eigenvalue of multiplicity 1;
(M3) there is no such nonzero matrix $X=(X_{i,j})\in \mathbb {R} ^{(n)}$ ${\ displaystyle X = (X_ {i, j}) \ in \ mathbb {R} ^ {(n)}}$ , what $MX=0$ ${\ displaystyle MX = 0}$ , So what $X_{i,j}=0$ ${\ displaystyle X_ {i, j} = 0}$ whenever $i=j$ ${\ displaystyle i = j}$ or $M_{i,j}\neq 0$ ${\ displaystyle M_ {i, j} \ neq 0}$ . ^[2] ^[1]

Classification of Known Graph Groups

From the point of view of the Colin de Verdier invariant, some well-known families of graphs have characteristic features:

$\mu (K_{1})=0$ ${\ displaystyle \ mu (K_ {1}) = 0}$ , $\mu (K_{n})=n-1$ ${\ displaystyle \ mu (K_ {n}) = n-1}$ , $\mu ({\overline {K_{n}}})=1$ ${\ displaystyle \ mu ({\ overline {K_ {n}}}) = 1}$ at $n>1$ ${\ displaystyle n> 1}$ ; ^[1] ^[2]
μ ≤ 1 if and only if G is a linear forest (a forest in which each component is a path, that is, the incidence of any vertex is at most 2); ^[1] ^[3]
μ ≤ 2 if and only if G is an outerplanar graph (all vertices are on the same face); ^[1] ^[2]
μ ≤ 3 if and only if G is a planar graph ; ^[1] ^[2]
μ ≤ 4 if and only if G is incoherently embeddable , that is, there are no two cycles in G for which, when mapped to Euclidean space (the link coefficient) is equal to zero. ^[1] ^[4]

The same groups of graphs show their distinctive features when analyzing the relationship between the invariant of a graph and the complement of this graph:

If the complement of a graph with n vertices is a linear forest, then μ ≥ n - 3 ; ^[1] ^[5]
If the complement of a graph with n vertices is an outerplanar graph, then μ ≥ n - 4 ; ^[1] ^[5]
If the complement of a graph with n vertices is a planar graph, then μ ≥ n - 5 . ^[1] ^[5]

Minors of the graphs

The minor of a graph G is the graph H obtained from G by successively removing vertices, removing edges, and compressing edges. The Kolen de Verdier invariant is monotonous with respect to the operation of taking the minor in the sense that ignoring the graph cannot increase its invariant:

If H is a minor of G , then

\mu (H)\leq \mu (G)

{\ displaystyle \ mu (H) \ leq \ mu (G)}

. ^[2]

By the Robertson – Seymour theorem , for any k there exists H , a finite set of graphs such that for any graph with an invariant of at most k, the graphs from H cannot be minors. Colin de Verdière 1990 lists the sets of such unacceptable minors for k ≤ 3; for k = 4, the set of invalid minors consists of seven graphs of the Petersen family by the definition of an incoherently embedded graph as a graph with μ ≤ 4 and without Petersen graphs as minors. ^[four]

Relationship to Chromatic Number

( Colin de Verdière 1990 ) suggested that any graph with de Verdier invariant μ can be colored using at most μ + 1 colors. For example, in linear forests (whose components are bipartite graphs), the invariant is 1; in outerplanar graphs, the invariant is 2, and they can be colored with three colors; planar graphs have an invariant of 3, and they can be colored with four colors .

For graphs with de Verdier invariant no more than four, the assumption is true; they are all incoherently embedded, and the fact that they are colored in five colors is a consequence of the proof of the Hadwiger conjecture for graphs without minors of type K ₆ in ( Robertson, Seymour & Thomas 1993 ).

Other properties

If the number of intersections of the graph is k , then de Verdier’s invariant for it will be no more than k + 3. For example, Kuratovsky’s graphs K ₅ and K _3.3 can be represented with one intersection, and the invariant for them will be no more than four . ^[2]

Notes

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ( van der Holst, Lovász & Schrijver 1999 ).
↑ ¹ ² ³ ⁴ ⁵ ⁶ ( Colin de Verdière 1990 ).
↑ In ( Colin de Verdière 1990 ) this case is not explicitly considered, but it follows explicitly from the results of the analysis of graphs that do not have minors of the form "triangle" and " claw ".
↑ ¹ ² ( Lovász & Schrijver 1998 ).
↑ ¹ ² ³ ( Kotlov, Lovász & Vempala 1997 ).

Links

Colin de Verdière, Y. (1990), " Sur un nouvel invariant des graphes et un critère de planarité ", Journal of Combinatorial Theory, Series B T. 50 (1): 11–21 , DOI 10.1016 / 0095-8956 (90 ) 90093-F . Translated by Neil Calkin as Colin de Verdière, Y. (1993), "On a new graph invariant and a criterion for planarity", in Robertson, Neil & Seymour, Paul , Graph Structure Theory: Proc. AMS – IMS – SIAM Joint Summer Research Conference on Graph Minors , vol. 147, Contemporary Mathematics, American Mathematical Society, p. 137–147 .
van der Holst, Hein; Lovász, László & Schrijver, Alexander (1999), "The Colin de Verdière graph parameter" , Graph Theory and Combinatorial Biology (Balatonlelle, 1996) , vol. 7, Bolyai Soc. Math. Stud., Budapest: János Bolyai Math. Soc., P. 29–85 , < http://www.cs.elte.hu/~lovasz/colinsurv.ps > .
Kotlov, Andrew; Lovász, László & Vempala, Santosh (1997), " The Colin de Verdiere number and sphere representations of a graph ", Combinatorica T. 17 (4): 483–521, doi : 10.1007 / BF01195002 , < http: // oldwww. cs.elte.hu/~lovasz/sphere.ps >
Lovász, László & Schrijver, Alexander (1998), " A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs ", Proceedings of the American Mathematical Society T. 126 (5): 1275–1285 , DOI 10.1090 / S0002- 9939-98-04244-0 .
Robertson, Neil ; Seymour, Paul & Thomas, Robin (1993), “ Hadwiger's conjecture for K ₆ -free graphs ”, Combinatorica T. 13: 279–361, doi : 10.1007 / BF01202354 , < http://www.math.gatech.edu/ ~ thomas / PAP / hadwiger.pdf > .

[hls99-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ( van der Holst, Lovász & Schrijver 1999 ).

[cdv90-2] ¹ ² ³ ⁴ ⁵ ⁶ ( Colin de Verdière 1990 ).

[3] In ( Colin de Verdière 1990 ) this case is not explicitly considered, but it follows explicitly from the results of the analysis of graphs that do not have minors of the form "triangle" and " claw ".

[ls98-4] ¹ ² ( Lovász & Schrijver 1998 ).

[klv97-5] ¹ ² ³ ( Kotlov, Lovász & Vempala 1997 ).