Colin de Verdière-gráfinvariáns forrásának megtekintése

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áf]]ra <math>\mu(G)</math> – [[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ék]]ei maximális [[multiplicitás]]ának vizsgálata volt.<ref name="hls99"/>

==Definíció==
Legyen <math>G=(V,E)</math> egy hurokmentes egyszerű gráf. [[Az általánosság megszorítása nélkül]] tegyük fel, hogy <math>V=\{1,\dots,n\}</math>. Ekkor <math>\mu(G)</math> bármely <math>M=(M_{i,j})\in\mathbb{R}^{(n)}</math> [[szimmetrikus mátrix]] legnagyobb [[Rang (lineáris algebra)|ko-rangja]] (egy <math>m\times n</math>-es mátrix ko-rangja <math>m-r</math>, ahol <math>r</math> a mátrix rangja), melyre:
# bármely <math>i,j</math>-re, ahol <math>i\neq j</math>: <math>M_{i,j}<0</math> ha <math>\{i,j\}\in E</math> és <math>M_{i,j}=0</math> ha <math>\{i,j\}\notin E</math>;
# ''M''-nek pontosan egyetlen negatív sajátértéke van, melynek multiplicitása 1;
# nem létezik olyan nemnulla <math>X=(X_{i,j})\in\mathbb{R}^{(n)}</math> mátrix, melyre <math>MX=0</math>, illetve olyan, melyre <math>X_{i,j}=0</math> ha akár <math>i=j</math>, akár <math>M_{i,j}\neq 0</math> igaz.<ref name="hls99"/><ref name="cdv90"/>

==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:
*{{nowrap|&mu; ≤ 0}} pontosan akkor áll fenn, ha ''G'' [[üres gráf|nem rendelkezik élekkel]];<ref name="hls99">{{harvtxt|van der Holst|Lovász|Schrijver|1999}}.</ref><ref name="cdv90"/>
*{{nowrap|&mu; ≤ 1}} pontosan akkor áll fenn, ha ''G'' [[lineáris erdő]] ([[útgráf|utak]] [[diszjunkt unió]]ja);<ref name="hls99"/><ref>{{harvtxt|Colin de Verdière|1990}} nem írja ezt explicit módon, de az általa használt jellemzésből – [[háromszöggráf|háromszög]] és [[mancs (gráfelmélet)|mancs]] minor nélküli gráfok – pontosan ez vezethető le.</ref>
*{{nowrap|&mu; ≤ 2}} pontosan akkor áll fenn, ha ''G'' [[külsíkgráf]];<ref name="hls99"/><ref name="cdv90"/>
*{{nowrap|&mu; ≤ 3}} pontosan akkor áll fenn, ha ''G'' [[síkbarajzolható gráf|síkbarajzolható]];<ref name="hls99"/><ref name="cdv90">{{harvtxt|Colin de Verdière|1990}}.</ref>
*{{nowrap|&mu; ≤ 4}} pontosan akkor áll fenn, ha ''G'' [[láncmentes beágyazás|láncmentesen beágyazható]].<ref name="hls99"/><ref name="ls98">{{harvtxt|Lovász|Schrijver|1998}}.</ref>

Ugyanezek a gráfcsaládok megjelennek a gráf Colin de Verdière-invariánsa és [[komplementer gráf]]jának szerkezete kapcsolatában:
*Ha egy ''n''-csúcsú gráf komplementere lineáris erdő, akkor {{nowrap|&mu; ≥ ''n'' &minus; 3}};<ref name="hls99"/><ref name="klv97">{{harvtxt|Kotlov|Lovász|Vempala|1997}}.</ref>
*Ha egy ''n''-csúcsú gráf komplementere külsíkgráf, akkor {{nowrap|&mu; ≥ ''n'' &minus; 4}};<ref name="hls99"/><ref name="klv97"/>
*Ha egy ''n''-csúcsú gráf komplementere síkbarajzolható, akkor {{nowrap|&mu; ≥ ''n'' &minus; 5}}.<ref name="hls99"/><ref name="klv97"/>

==Gráfminorok==
Egy gráf [[minor (gráfelmélet)|minora]] az eredeti gráfból [[élösszehúzás|é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 <math>\mu(H)\leq\mu(G)</math>.<ref name="cdv90"/>
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. {{harvtxt|Colin de Verdière|1990}} listázza ezeket a [[Tiltott gráfok szerinti osztályozás|tiltott minorokat]] ''k''&nbsp;≤&nbsp;3-ra; ''k''&nbsp;=&nbsp;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 &mu;&nbsp;≤&nbsp;4 és melyeknek nincs Petersen-családbeli minoruk.<ref name="ls98"/>

==Kromatikus szám==
{{harvtxt|Colin de Verdière|1990}} sejtése szerint egy &mu; Colin de Verdière-invariánsú gráf [[gráfok színezése|színezhető]] legfeljebb &mu;&nbsp;+&nbsp;1 színnel. Például a lineáris erdők invariánsa 1, és [[páros gráf|2-színezhetők]]; a [[külsíkgráf]]ok invariánsa kettő, és 3-színezhetők, és a [[síkbarajzolható gráf]]ok (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 (gráfelmélet)|Hadwiger-sejtés]] ''K''<sub>6</sub>-minormentes gráfokra való bizonyításának, amit {{harvtxt|Robertson|Seymour|Thomas|1993}} végzett el.

==Egyéb tulajdonságok==
Ha egy gráf [[Metszési szám (gráfelmélet)|metszési száma]] <math>k</math>, akkor Colin de Verdière-invariánsa legfeljebb <math>k+3</math>. Például a két [[Kazimierz Kuratowski|Kuratowski]]-féle gráfot, a <math>K_5</math>öt és a <math>K_{3,3}</math>-at le lehet rajzolni egyetlen metszéssel, Colin de Verdière-invariánsuk ezért legfeljebb négy.<ref name="cdv90"/>

==Boxicitással való kapcsolata==
Ugyanazon gráf Colin de Verdière-invariánsa és [[boxicitás]]a között [[Louis Esperet]] a következő összefüggést igazolta:
:<math>\operatorname{box}(G) = O(\mu(G)^4(\log(\mu(G))^2)</math>,
továbbá valószínűsíti, hogy a boxicitás legfeljebb a Colin de Verdière-invariánssal egyenlő.<ref>{{cite arXiv |last=Esperet |first=Louis |date=2015 |title=Boxicity and Topological Invariants|eprint=1503.05765 |class=math.CO}}</ref>

==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 rangja|gráf minimális rangját]], a [[gráf minimális szemidefinit rangja|gráf minimális szemidefinit rangját]] és a [[gráf minimális ferde rangja|gráf minimális ferde rangját]].

==Fordítás==
* {{fordítás|en|Colin de Verdière graph invariant|oldid=830485598|n=a|4=angol}}

==Jegyzetek==
{{reflist}}

*{{citation
 | last = Colin de Verdière | first = Y. | author-link = Yves Colin de Verdière
 | doi = 10.1016/0095-8956(90)90093-F
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 11–21
 | title = Sur un nouvel invariant des graphes et un critère de planarité
 | volume = 50
 | year = 1990}}. Translated by Neil Calkin as {{citation
 | last = Colin de Verdière | first = Y. | author-link = Yves Colin de Verdière
 | contribution = On a new graph invariant and a criterion for planarity
 | editor1-last = Robertson | editor1-first = Neil | editor1-link = Neil Robertson (matematikus)
 | editor2-last = Seymour | editor2-first = Paul | editor2-link = Paul Seymour (mathematician)
 | pages = 137–147
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
 | volume = 147
 | year = 1993}}.
*{{citation
 | last1 = van der Holst
 | first1 = Hein
 | last2 = Lovász
 | first2 = László
 | author2-link = Lovász László (matematikus)
 | last3 = Schrijver
 | first3 = Alexander
 | author3-link = Alexander Schrijver
 | contribution = The Colin de Verdière graph parameter
 | location = Budapest
 | pages = 29–85
 | publisher = János Bolyai Math. Soc.
 | series = Bolyai Soc. Math. Stud.
 | title = Graph Theory and Combinatorial Biology (Balatonlelle, 1996)
 | url = http://www.cs.elte.hu/~lovasz/colinsurv.ps
 | volume = 7
 | year = 1999
 }} {{Wayback|url=http://www.cs.elte.hu/~lovasz/colinsurv.ps |date=20160303165118 }}.
*{{citation
 | last1 = Kotlov
 | first1 = Andrew
 | last2 = Lovász
 | first2 = László
 | author2-link = Lovász László (matematikus)
 | last3 = Vempala
 | first3 = Santosh
 | doi = 10.1007/BF01195002
 | issue = 4
 | journal = Combinatorica
 | pages = 483–521
 | title = The Colin de Verdiere number and sphere representations of a graph
 | url = http://oldwww.cs.elte.hu/~lovasz/sphere.ps
 | volume = 17
 | year = 1997
 }} {{Wayback|url=http://oldwww.cs.elte.hu/~lovasz/sphere.ps |date=20160303190340 }}
*{{citation
 | last1 = Lovász | first1 = László | author1-link = Lovász László (matematikus)
 | last2 = Schrijver | first2 = Alexander | author2-link = Alexander Schrijver
 | doi = 10.1090/S0002-9939-98-04244-0
 | issue = 5
 | journal = [[Proceedings of the American Mathematical Society]]
 | pages = 1275–1285
 | title = A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
 | volume = 126
 | year = 1998}}.
*{{citation | last1=Robertson | first1=Neil | author1-link=Neil Robertson (matematikus) | last2=Seymour | first2=Paul | author2-link=Paul Seymour (mathematician) | last3=Thomas | first3=Robin | author3-link=Robin Thomas (mathematician) | title=Hadwiger's conjecture for K<sub>6</sub>-free graphs | url=http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf | year=1993 | journal=[[Combinatorica]] | volume=13 | pages=279–361 | doi=10.1007/BF01202354 | accessdate=2018-03-30 | archívurl=https://web.archive.org/web/20090410233641/http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf | archívdátum=2009-04-10 }}.

[[Kategória:Gráfinvariánsok]]
[[Kategória:Gráfminorok]]