Colin de Verdière-gráfinvariáns

A matematika, azon belül a gráfelmélet területén a Colin de Verdière-gráfinvariáns vagy Colin de Verdière-invariáns – jelölése tetszőleges G gráfra $\mu (G)$ – Yves Colin de Verdière által 1990-ben bevezetett gráfparaméter. Meghatározásának motivációja egyes Schrödinger-operátorok második sajátértékei maximális multiplicitásának vizsgálata volt.

Definíció

Legyen $G=(V,E)$ egy hurokmentes egyszerű gráf. Az általánosság megszorítása nélkül tegyük fel, hogy $V=\{1,\dots ,n\}$. Ekkor $\mu (G)$ bármely $M=(M_{i,j})\in \mathbb {R} ^{(n)}$ szimmetrikus mátrix legnagyobb ko-rangja (egy $m\times n$-es mátrix ko-rangja $m-r$, ahol $r$ a mátrix rangja), melyre:

1. bármely $i,j$-re, ahol $i\neq j$: $M_{i,j}<0$ ha $\{i,j\}\in E$ és $M_{i,j}=0$ ha $\{i,j\}\notin E$;
2. M-nek pontosan egyetlen negatív sajátértéke van, melynek multiplicitása 1;
3. nem létezik olyan nemnulla $X=(X_{i,j})\in \mathbb {R} ^{(n)}$ mátrix, melyre $MX=0$, illetve olyan, melyre $X_{i,j}=0$ ha akár $i=j$, akár $M_{i,j}\neq 0$ igaz.

Ismert gráfcsaládok karakterizációi

Néhány jól ismert gráfcsalád karakterizálható Colin de Verdière-invariánsuk szerint:

• μ ≤ 0 pontosan akkor áll fenn, ha G nem rendelkezik élekkel;
• μ ≤ 1 pontosan akkor áll fenn, ha G lineáris erdő (utak diszjunkt uniója);
• μ ≤ 2 pontosan akkor áll fenn, ha G külsíkgráf;
• μ ≤ 3 pontosan akkor áll fenn, ha G síkbarajzolható;
• μ ≤ 4 pontosan akkor áll fenn, ha G láncmentesen beágyazható.

Ugyanezek a gráfcsaládok megjelennek a gráf Colin de Verdière-invariánsa és komplementer gráfjának szerkezete kapcsolatában:

• Ha egy n-csúcsú gráf komplementere lineáris erdő, akkor μ ≥ n − 3;
• Ha egy n-csúcsú gráf komplementere külsíkgráf, akkor μ ≥ n − 4;
• Ha egy n-csúcsú gráf komplementere síkbarajzolható, akkor μ ≥ n − 5.

Gráfminorok

Egy gráf minora az eredeti gráfból élek összehúzásával, élek és csúcsok törlésével kapott gráf. A Colin de Verdière-invariáns minor-monoton, ami azt jelenti, hogy a minorképzés műveletével a gráf invariánsát csak csökkenteni vagy változatlanul hagyni lehet:

Ha H minora G-nek, akkor $\mu (H)\leq \mu (G)$.

A Robertson–Seymour-tétel értelmében minden k-hoz létezik gráfok H véges halmaza, melyre igaz, hogy a legfeljebb k invariánsú gráfok megegyeznek a minorként H egyik tagját sem tartalmazó gráfokkal. (Colin de Verdière 1990) listázza ezeket a tiltott minorokat k ≤ 3-ra; k = 4-re a tiltott minorok halmaza a Petersen-gráfcsalád hét gráfjából áll, a csomómentesen beágyazható gráfok két karakterizációja alapján, miszerint a gráfok, melyekre μ ≤ 4 és melyeknek nincs Petersen-családbeli minoruk.

Kromatikus szám

(Colin de Verdière 1990) sejtése szerint egy μ Colin de Verdière-invariánsú gráf színezhető legfeljebb μ + 1 színnel. Például a lineáris erdők invariánsa 1, és 2-színezhetők; a külsíkgráfok invariánsa kettő, és 3-színezhetők, és a síkbarajzolható gráfok (a négyszíntétel értelmében) 4-színezhetők.

A legfeljebb 4-es Colin de Verdière-invariánsú gráfokra a sejtés igaz; az, hogy a csomómentesen beágyazható gráfok kromatikus száma legfeljebb öt, következménye a Hadwiger-sejtés K₆-minormentes gráfokra való bizonyításának, amit (Robertson, Seymour & Thomas 1993) végzett el.

Egyéb tulajdonságok

Ha egy gráf metszési száma $k$, akkor Colin de Verdière-invariánsa legfeljebb $k+3$. Például a két Kuratowski-féle gráfot, a $K_{5}$öt és a $K_{3,3}$-at le lehet rajzolni egyetlen metszéssel, Colin de Verdière-invariánsuk ezért legfeljebb négy.

Boxicitással való kapcsolata

Ugyanazon gráf Colin de Verdière-invariánsa és boxicitása között Louis Esperet a következő összefüggést igazolta:

$\operatorname {box} (G)=O(\mu (G)^{4}(\log(\mu (G))^{2})$,

továbbá valószínűsíti, hogy a boxicitás legfeljebb a Colin de Verdière-invariánssal egyenlő.

Befolyás

A Colin de Verdière-invariánst a gráfhoz tartozó speciális mátrixosztály alapján definiálják, nem csak egyetlen, a gráfhoz tartozó mátrixból. Hasonló módon definiáltak néhány más gráfparamétert is, mint például a gráf minimális rangját, a gráf minimális szemidefinit rangját és a gráf minimális ferde rangját.

Fordítás

• Ez a szócikk részben vagy egészben a Colin de Verdière graph invariant című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Colin de Verdière, Y. (1990), "Sur un nouvel invariant des graphes et un critère de planarité", Journal of Combinatorial Theory, Series B 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, pp. 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., pp. 29–85, <http://www.cs.elte.hu/~lovasz/colinsurv.ps> Archiválva 2016. március 3-i dátummal a Wayback Machine-ben.
• Kotlov, Andrew; Lovász, László & Vempala, Santosh (1997), "The Colin de Verdiere number and sphere representations of a graph", Combinatorica 17 (4): 483–521, doi:10.1007/BF01195002, <http://oldwww.cs.elte.hu/~lovasz/sphere.ps> Archiválva 2016. március 3-i dátummal a Wayback Machine-ben
• 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 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 13: 279–361, doi:10.1007/BF01202354, <http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf>. Hozzáférés ideje: 2018-03-30.