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 ${\displaystyle \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.^[1]

Definíció

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

1. bármely ${\displaystyle i,j}$-re, ahol ${\displaystyle i\neq j}$: ${\displaystyle M_{i,j}<0}$ ha ${\displaystyle \{i,j\}\in E}$ és ${\displaystyle M_{i,j}=0}$ ha ${\displaystyle \{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 ${\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)}}$ mátrix, melyre ${\displaystyle MX=0}$, illetve olyan, melyre ${\displaystyle X_{i,j}=0}$ ha akár ${\displaystyle i=j}$, akár ${\displaystyle M_{i,j}\neq 0}$ igaz.^[1][2]

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][2]
• μ ≤ 1 pontosan akkor áll fenn, ha G lineáris erdő (utak diszjunkt uniója);^[1][3]
• μ ≤ 2 pontosan akkor áll fenn, ha G külsíkgráf;^[1][2]
• μ ≤ 3 pontosan akkor áll fenn, ha G síkbarajzolható;^[1][2]
• μ ≤ 4 pontosan akkor áll fenn, ha G láncmentesen beágyazható.^[1][4]

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;^[1][5]
• Ha egy n-csúcsú gráf komplementere külsíkgráf, akkor μ ≥ n − 4;^[1][5]
• Ha egy n-csúcsú gráf komplementere síkbarajzolható, akkor μ ≥ n − 5.^[1][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 ${\displaystyle \mu (H)\leq \mu (G)}$.^[2]

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.^[4]

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 ${\displaystyle k}$, akkor Colin de Verdière-invariánsa legfeljebb ${\displaystyle k+3}$. Például a két Kuratowski-féle gráfot, a ${\displaystyle K_{5}}$öt és a ${\displaystyle K_{3,3}}$-at le lehet rajzolni egyetlen metszéssel, Colin de Verdière-invariánsuk ezért legfeljebb négy.^[2]

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:

${\displaystyle \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ő.^[6]

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

1. (van der Holst, Lovász & Schrijver 1999).
2. (Colin de Verdière 1990).
3. (Colin de Verdière 1990) nem írja ezt explicit módon, de az általa használt jellemzésből – háromszög és mancs minor nélküli gráfok – pontosan ez vezethető le.
4. (Lovász & Schrijver 1998).
5. (Kotlov, Lovász & Vempala 1997).
6. Esperet, Louis (2015). "Boxicity and Topological Invariants". arXiv:1503.05765 [math.CO].

• 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.