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 {ℝ}^{(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\ne 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 {ℝ}^{(n)}$ mátrix, melyre $MX=0$, illetve olyan, melyre $X_{i,j}=0$ ha akár $i=j$, akár $M_{i,j}\ne 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:

• Sablon:Nowrap pontosan akkor áll fenn, ha G nem rendelkezik élekkel;
• Sablon:Nowrap pontosan akkor áll fenn, ha G lineáris erdő (utak diszjunkt uniója);
• Sablon:Nowrap pontosan akkor áll fenn, ha G külsíkgráf;
• Sablon:Nowrap pontosan akkor áll fenn, ha G síkbarajzolható;
• Sablon:Nowrap 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 Sablon:Nowrap;
• Ha egy n-csúcsú gráf komplementere külsíkgráf, akkor Sablon:Nowrap;
• Ha egy n-csúcsú gráf komplementere síkbarajzolható, akkor Sablon:Nowrap.

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)\le \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. Sablon:Harvtxt 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

Sablon:Harvtxt 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 Sablon:Harvtxt 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:

$\mathrm{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

• Sablon:Fordítás

Jegyzetek

• Sablon:Citation. Translated by Neil Calkin as Sablon:Citation.
• Sablon:Citation Sablon:Wayback.
• Sablon:Citation Sablon:Wayback
• Sablon:Citation.
• Sablon:Citation.