Colin de Verdier invariant

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. januar 2018; checks kræver 7 redigeringer .

Colin de Verdière-invarianten er en karakteristik af en graf defineret for enhver graf G , introduceret af Yves Colin de Verdière i 1990 i færd med at studere multipliciteten af den anden egenværdi af nogle Schrödinger-operatorer . [en] $\mu (G)$

Definition

Lad være en simpel (ikke indeholdende sløjfer og flere kanter) acyklisk graf. Uden tab af generalitet, lad os navngive sættet af knudepunkter som følger: . Så er den største corrank af enhver matrix sådan, at: $G=(V,E)$ $V=\{1,\dots ,n\}$ $\mu (G)$ ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)))$

(M1) for enhver , hvor : , hvis i og j er tilstødende, og , ellers $i,j$ $i\neq j$ $M_{i,j}<0$ $M_{i,j}=0$
(M2) M har nøjagtig én egenværdi af multiplicitet 1;
(M3) der er ingen sådan ikke-nul matrix sådan, at , og at når eller . [2] [1] ${\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)))$ $MX=0$ $X_{i,j}=0$ $i=j$ $M_{i,j}\neq 0$

Klassifikation af kendte grupper af grafer

Fra Colin de Verdière-invariantens synspunkt har nogle velkendte familier af grafer karakteristiske træk:

$\mu (K_{1})=0$ , , ved ; [1] [2] $\mu (K_{n})=n-1$ $\mu ({\overline {K_{n))})=1$ $n>1$
μ ≤ 1 hvis og kun hvis G er en lineær skov (en skov, hvor hver komponent er en sti, dvs. forekomsten af ethvert toppunkt er højst 2); [1] [3]
μ ≤ 2 hvis og kun hvis G er en ydreplanar graf (alle toppunkter ligger på samme flade); [1] [2]
μ ≤ 3 hvis og kun hvis G er en plan graf ; [1] [2]
μ ≤ 4 , hvis og kun hvis G er inkohærent indlejrbar , dvs. der er ikke to cyklusser i G , for hvilke, når de er afbildet på det euklidiske rum (sammenkædningskoefficienten) er nul. [1] [4]

De samme grupper af grafer viser deres karakteristiske træk, når man analyserer forholdet mellem grafens invariante og komplementet af denne graf:

Hvis komplementet af en graf med n toppunkter er en lineær skov, så er μ ≥ n − 3 ; [1] [5]
Hvis komplementet til en graf med n toppunkter er en ydreplanar graf, så μ ≥ n − 4 ; [1] [5]
Hvis komplementet til en graf med n toppunkter er en plan graf, så er μ ≥ n − 5 . [1] [5]

Tæl mindreårige

En mindre af en graf G er en graf H opnået fra G ved successiv fjernelse af hjørner, fjernelse af kanter og sammentrækning af kanter. Colin de Verdière-invarianten er monoton under operationen med at tage en mol i den forstand, at minorisering af en graf ikke kan øge dens invariant:

Hvis H er en mol af G , så . [2]

\mu (H)\leq \mu (G)

Ved Robertson-Seymour-sætningen eksisterer der for enhver k H , et begrænset sæt af grafer, således at for enhver graf med højst invariant k , kan grafer fra H ikke være mindre. Papiret ( Colin de Verdière 1990 ) lister sætene af sådanne ugyldige mindreårige for k ≤ 3; for k = 4 består sættet af ugyldige mindreårige af syv Petersen-familiegrafer per definition af en usammenhængende graf som en graf med μ ≤ 4 og ingen Petersen-grafer som mindreårige. [fire]

Forholdet til kromatisk tal

( Colin de Verdière 1990 ) foreslog, at enhver graf med de Verdière invariant μ kan farves med højst μ + 1 farver. For eksempel har lineære skove (hvis komponenter er todelte grafer) en invariant på 1; ydre planære grafer har en invariant på 2 og kan farves med tre farver; plane grafer har en invariant på 3 og kan farves med fire farver .

For grafer med de Verdier invariant højst fire, er antagelsen sand; de er alle usammenhængende indlejrbare, og det faktum, at de er femfarvede, er en konsekvens af beviset for Hadwigers formodning for grafer uden bifag af type K 6 in ( Robertson, Seymour & Thomas 1993 ).

Andre egenskaber

Hvis antallet af skæringspunkter i en graf er k , så vil de Verdier-invarianten for den højst være k + 3. Kuratowski-graferne K 5 og K 3,3 kan f.eks. afbildes med ét skæringspunkt, og invarianten for de bliver højst fire. [2]

Noter

↑ 1 2 3 4 5 6 7 8 9 10 ( van der Holst, Lovász & Schrijver 1999 ).
↑ 1 2 3 4 5 6 ( Colin de Verdière 1990 ).
↑ I ( Colin de Verdière 1990 ) er denne sag ikke eksplicit taget i betragtning, men den følger eksplicit af resultaterne af analysen af grafer, der ikke har biord af formen "trekant" og " klo ".
↑ 1 2 ( Lovász & Schrijver 1998 ).
↑ 1 2 3 ( Kotlov, Lovász & Vempala 1997 ).

Links

Colin de Verdière, Y. (1990), Sur un nouvel invariant des graphes et un critère de planarité , Journal of Combinatorial Theory, Series B bind 50 (1): 11–21 , DOI 10.1016/0095-8956(90)9009 -F . Oversat af Neil Calkin som Colin de Verdière, Y. (1993), On a new graph invariant and a criterion for planarity, i 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, s. 137–147 .
van der Holst, Hein; Lovász, László & Schrijver, Alexander (1999), Colin de Verdière-grafparameteren , Graph Theory and Combinatorial Biology (Balatonlelle, 1996) , vol. 7, Bolyai Soc. Matematik. Stud., Budapest: Janos Bolyai Math. Soc., s. 29–85 , < http://www.cs.elte.hu/~lovasz/colinsurv.ps > .
Kotlov, Andrew; Lovász, László & Vempala, Santosh (1997), Colin de Verdieres tal- og sfærerepræsentationer af en graf , Combinatorica T. 17 (4): 483–521, doi : 10.1007/BF01195002 , < http://oldwww.cs. elte.hu/~lovasz/sphere.ps >
Lovász, László & Schrijver, Alexander (1998), A Borsuk theorem for antipodale links and a spectral characterization of linklessly embeddable graphs , Proceedings of the American Mathematical Society bind 126 (5): 1275–1285 , DOI 10.0902-/9S902-/9S902-/ 98-04244-0 .
Robertson, Neil ; Seymour, Paul & Thomas, Robin (1993), Hadwigers formodning for K 6 - fri grafer , Combinatorica vol. 13: 279–361, doi : 10.1007/BF01202354 , < http://www.math.gatech.edu/~thomas /PAP/hadwiger.pdf > .