Invariant de Colin de Verdière

L'invariant de Colin de Verdière est un paramètre de théorie des graphes, défini pour tout graphe, introduit par Yves Colin de Verdière en 1990. Il a été motivé par l'étude de la multiplicité maximale de la seconde valeur propre de certains opérateurs hamiltoniens^[1].

Définition

Soit ${\displaystyle G=(V,E)}$ un graphe simple sans boucle. On suppose sans perte de généralité que ${\displaystyle V=\{1,\dots ,n\}}$. L'invariant de Colin de Verdière ${\displaystyle \mu (G)}$ est le plus grand corang (en) d'une matrice symétrique ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{n\times n}}$ telle que :

• (M1) pour tout ${\displaystyle i\neq j}$, ${\displaystyle M_{i,j}<0}$ si ${\displaystyle \{i,j\}\in E}$, et ${\displaystyle M_{i,j}=0}$ si ${\displaystyle \{i,j\}\notin E}$ ;
• (M2) ${\displaystyle M}$ a exactement une valeur propre négative, de multiplicité 1 ;
• (M3) il n'existe pas de matrices ${\displaystyle X=(X_{i,j})\in \mathbb {R} ^{n\times n}}$ avec ${\displaystyle MX=0}$ et telle que ${\displaystyle X_{i,j}=0}$ lorsque ${\displaystyle i=j}$ ou ${\displaystyle M_{i,j}\neq 0}$^[1],[2].

Caractérisation des familles de graphes connues

Plusieurs familles de graphes bien connues peuvent être caractérisées en termes de leurs invariants de Colin de Verdière :

• ${\displaystyle \mu (G)\leq 0}$ si et seulement si ${\displaystyle G}$ est le graphe nul (sans arêtes)^[1],[2];
• ${\displaystyle \mu (G)\leq 1}$ si et seulement si ${\displaystyle G}$ est une forêt linéaire (en) (union disjointe de chaînes)^[1],[3];
• ${\displaystyle \mu (G)\leq 2}$ si et seulement si ${\displaystyle G}$ est un graphe planaire extérieur^[1],[2];
• ${\displaystyle \mu (G)\leq 3}$ si et seulement si ${\displaystyle G}$ est un graphe planaire^[1],[2];
• ${\displaystyle \mu (G)\leq 4}$ si et seulement si ${\displaystyle G}$ est un graphe qui admet un plongement sans entrelacs (en)^[1],[4]

Ces mêmes familles de graphes apparaissent également dans les connexions entre l'invariant de Colin de Verdière d'un graphe et la structure de son graphe complémentaire :

• Si le complément d'un graphe à ${\displaystyle n}$ sommets est une forêt linéaire, alors ${\displaystyle \mu \geq n-3}$^[1],[5];
• Si le complément d'un graphe à ${\displaystyle n}$ sommets est une graphe planaire extérieur, alors ${\displaystyle \mu \geq n-4}$^[1],[5];
• Si le complément d'un graphe à ${\displaystyle n}$ sommets est une graphe planaire, alors ${\displaystyle \mu \geq n-4}$^[1],[5].

Mineurs

Un mineur d'un graphe est un graphe formé à partir du graphe de départ en contractant des arêtes et en supprimant des arêtes et des sommets. L'invariant de Colin de Verdière est décroissant par passage aux mineurs, ce qui signifie qu'un mineur d'un graphe donné a un invariant plus petit que le graphe de départ :

On a ${\displaystyle \mu (H)\leq \mu (G)}$ pour tout mineur ${\displaystyle H}$ de ${\displaystyle G}$^[2].

Par le théorème de Robertson-Seymour, il existe, pour tout k, un ensemble fini H de graphes tels que les graphes d'invariant au plus k sont exactement les graphes dont aucun mineur n'est dans H. Colin de Verdière 1990 liste ces ensembles de mineurs exclus pour k ≤ 3; for k = 4 l'ensemble des mineurs exclus est composé des sept graphes de la P, due aux deux caractérisations des plongements sans entrelacs (en) comme graphes avec μ ≤ 4 et comme graphes sans mineur dans la famille de^[4]. Pour k = 5 l'ensemble des mineurs exclus comprend 78 graphes de la famille de Heawood, et on suppose qu'il n'y a pas d'autres^[6].

Nombre chromatique

Colin de Verdière 1990 a conjecturé que tout graphe avec invariant de Colin de Verdière μ peut être coloré avec au plus μ + 1 couleurs. Par exemple; les forêts linéaires ont un invariant inférieur à 1 et sont 2-coloriables; un graphe planaire extérieur a un invariant inférieur à deux, et est 3-coloriable ; les graphes planaires ont un invariant inférieur à 3 et (par le théorème des quatre couleurs) sont 4-coloriables.

Pour les graphes d'invariant au plus quatre, la conjecture reste vraie ; ce sont les graphe avec plongement sans entrelacs, et le fait qu'ils ont un nombre chromatique au plus cinq est un conséquence de la preuve, par Robertson, Seymour et Thomas^[7], de la Conjecture de Hadwiger pour les graphes sans mineur K₆.

Autres propriétés

Si un graphe a un nombre de croisements ${\displaystyle k}$, son invariant de Colin de Verdière est au plus ${\displaystyle k+3}$. Par exemple, les deux graphes de Kuratowski ${\displaystyle K_{5}}$ et ${\displaystyle K_{3,3}}$ peuvent être tracés avec un seul croisement, et ont un invariant de au plus 4^[2].

Influence

L'invariant de Colin de Verdière est défini à partir d'une famille particulière de matrices associées à un graphe plutôt qu'une matrice directement définie par le graphe. Dans cet ordre d'idées, d'autres paramètres de graphes ont été définis et étudiés, tel que le rang minimum d'un graphe (en), le rang minimum semidéfini d'un graphe (en) et le rang gauche minimum d'un graphe (en).

Notes

1. van der Holst, Lovász et Schrijver 1999.
2. Colin de Verdière 1990.
3. Colin de Verdière 1990 n'énonce pas explicitement ce cas, mais il découle de sa caractérisation de ces graphes comme étant les graphes sans mineurs qui sont des graphes triangle ou graphes étoie.
4. Lovász et Schrijver 1998.
5. ^,Kotlov, Lovász et Vempala 1997.
6. Hein van der Holst, « Graphs and obstructions in four dimensions », Journal of Combinatorial Theory, Series B, vol. 96, n^o 3,‎ 2006, p. 388-404 (DOI 10.1016/j.jctb.2005.09.004, lire en ligne)
7. Robertson, Seymour et Thomas 1993.

Références

• Yves Colin de Verdière, « Sur un nouvel invariant des graphes et un critère de planarité », Journal of Combinatorial Theory, Series B, vol. 50, n^o 1,‎ 1990, p. 11–21 (DOI 10.1016/0095-8956(90)90093-F). Traduit par Neil Calkin : Yves Colin de Verdière, « On a new graph invariant and a criterion for planarity », dans Neil Robertson et Paul Seymour (éditeurs), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, American Mathematical Society, coll. « Contemporary Mathematics » (n^o 147), 1993, p. 137–147.
• Hein van der Holst, László Lovász et Alexander Schrijver, « The Colin de Verdière graph parameter », János Bolyai Math. Soc., Budapest, vol. 7,‎ 1999, p. 29–85 (lire en ligne).
• Andrew Kotlov, László Lovász et Santosh Vempala, « The Colin de Verdiere number and sphere representations of a graph », Combinatorica, vol. 17, n^o 4,‎ 1997, p. 483–521 (DOI 10.1007/BF01195002, lire en ligne)
• László Lovász et Alexander Schrijver, « A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs », Proceedings of the American Mathematical Society, vol. 126, n^o 5,‎ 1998, p. 1275–1285 (DOI 10.1090/S0002-9939-98-04244-0).
• Neil Robertson, Paul Seymour et Robin Thomas, « Hadwiger's conjecture for K₆-free graphs », Combinatorica, vol. 13,‎ 1993, p. 279–361 (DOI 10.1007/BF01202354, lire en ligne).

Autres publications

• László Lovász, Graphs and geometry, American Mathematical Soc., coll. « Colloquium Publications » (n^o 65), 2019, 444 p. (ISBN 978-1-4704-5087-8, lire en ligne), « Chap. 16 : The Colin de Verdière Number ».
• Vojtêch Kaluẑa et Martin Tancer, « Even maps, the Colin de Verdiere number and representations of graphs », Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,‎ 2020, p. 2642-2657.