Colin de Verdier invariant

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 januari 2018; kontroller kräver 7 redigeringar .

Colin de Verdière-invarianten är en egenskap hos en graf definierad för vilken graf G som helst , introducerad av Yves Colin de Verdière 1990 i färd med att studera mångfalden av det andra egenvärdet för några Schrödinger-operatorer . [ett] $\mugg)$

Definition

Låt vara en enkel (som inte innehåller loopar och flera kanter) acyklisk graf. Utan förlust av generalitet, låt oss namnge uppsättningen av hörn enligt följande: . Då är den största corranken av någon matris så att: $G=(V,E)$ $V=\{1,\dots ,n\}$ $\mugg)$ ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)))$

(M1) för alla , där : , om i och j är angränsande, och , annars $I j$ $i\neq j$ $M_{i,j}<0$ $M_{i,j}=0$
(M2) M har exakt ett egenvärde med multiplicitet 1;
(M3) det finns ingen sådan matris som inte är noll så att , och att närhelst 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$

Klassificering av kända grupper av grafer

Ur Colin de Verdière-invariantens synvinkel har några välkända familjer av grafer karakteristiska egenskaper:

$\mu (K_{1})=0$ , , vid ; [1] [2] $\mu (K_{n})=n-1$ $\mu ({\overline {K_{n))})=1$ $n>1$
μ ≤ 1 om och endast om G är en linjär skog (en skog där varje komponent är en bana, det vill säga förekomsten av någon vertex är högst 2); [1] [3]
μ ≤ 2 om och endast om G är en ytterplanär graf (alla hörn ligger på samma yta); [1] [2]
μ ≤ 3 om och endast om G är en plan graf ; [1] [2]
μ ≤ 4 om och endast om G är inkoherent inbäddningsbar , det vill säga det finns inga två cykler i G för vilka, när de mappas till det euklidiska rymden (länkningskoefficienten) är noll. [1] [4]

Samma grupper av grafer visar sina särdrag när man analyserar förhållandet mellan grafens invariant och komplementet till denna graf:

Om komplementet till en graf med n hörn är en linjär skog, då μ ≥ n − 3 ; [1] [5]
Om komplementet till en graf med n hörn är en ytterplanär graf, då μ ≥ n − 4 ; [1] [5]
Om komplementet till en graf med n hörn är en plan graf, då μ ≥ n − 5 . [1] [5]

Räkna minderåriga

En moll av en graf G är en graf H erhållen från G genom successiv borttagning av hörn, borttagning av kanter och sammandragning av kanter. Colin de Verdière-invarianten är monoton under operationen att ta en moll i den meningen att minorisering av en graf inte kan öka dess invariant:

Om H är en moll av G , då . [2]

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

Enligt Robertson-Seymour-satsen finns det för varje k H , en ändlig uppsättning grafer så att för varje graf med invariant högst k , kan grafer från H inte vara moll. Tidningen ( Colin de Verdière 1990 ) listar uppsättningarna av sådana ogiltiga minderåriga för k ≤ 3; för k = 4, består uppsättningen av ogiltiga minderåriga av sju Petersen-familjegrafer per definition av en disjunkt inbäddad graf som en graf med μ ≤ 4 och inga Petersen-grafer som mindre. [fyra]

Förhållande med kromatiskt tal

( Colin de Verdière 1990 ) föreslog att vilken graf som helst med de Verdière invariant μ kan färgas med högst μ + 1 färger. Till exempel har linjära skogar (vars komponenter är tvådelade grafer) en invariant på 1; ytterplanära grafer har en invariant på 2 och kan färgas med tre färger; Plana grafer har en invariant på 3 och kan färgas med fyra färger .

För grafer med de Verdier invariant högst fyra, är antagandet sant; de är alla osammanhängande inbäddningsbara, och det faktum att de är femfärgsbara är en konsekvens av beviset på Hadwigers gissning för grafer utan biroller av typ K 6 in ( Robertson, Seymour & Thomas 1993 ).

Andra egenskaper

Om antalet skärningspunkter för en graf är k , så kommer de Verdier-invarianten för den att vara högst k + 3. Kuratowski-graferna K 5 och K 3,3 kan till exempel avbildas med en skärningspunkt, och invarianten för de blir högst fyra. [2]

Anteckningar

↑ 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 ) beaktas inte detta fall explicit, men det följer uttryckligen av resultaten av analysen av grafer som inte har molor av formen "triangel" och " klo ".
↑ 1 2 ( Lovász & Schrijver 1998 ).
↑ 1 2 3 ( Kotlov, Lovász & Vempala 1997 ).

Länkar

Colin de Verdière, Y. (1990), Sur un nouvel invariant des graphes et un critère de planarité , Journal of Combinatorial Theory, Series B vol 50 (1): 11–21 , DOI 10.1016/0095-8956(90)9009 -F . Översatt av 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, sid. 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. Matematik. Stud., Budapest: Janos Bolyai Math. Soc., sid. 29–85 , < http://www.cs.elte.hu/~lovasz/colinsurv.ps > .
Kotlov, Andrew; Lovász, László & Vempala, Santosh (1997), The Colin de Verdiere number and sphere representations of a graph , 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 antipodal links and a spectral characterization of linklessly embedded graphs , Proceedings of the American Mathematical Society vol 126 (5): 1275–1285 , DOI 10.9090-/9S902-/9S902-/9S. 98-04244-0 .
Robertson, Neil ; Seymour, Paul & Thomas, Robin (1993), Hadwiger's conjecture for K 6 -free graphs , Combinatorica vol. 13: 279–361, doi : 10.1007/BF01202354 , < http://www.math.gatech.edu/~thomas /PAP/hadwiger.pdf > .