Colin de Verdier invariantti

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. tammikuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 7 muokkausta .

Colin de Verdièren invariantti on mille tahansa graafille G määritetyn graafin ominaisuus , jonka Yves Colin de Verdière esitteli vuonna 1990 tutkiessaan joidenkin Schrödinger-operaattoreiden toisen ominaisarvon monikertaisuutta . [yksi] $\mu (G)$

Määritelmä

Antaa olla yksinkertainen (ei sisällä silmukoita ja useita reunoja) asyklinen graafi. Yleisyyttä menettämättä nimetään kärkijoukko seuraavasti: . Sitten on minkä tahansa matriisin suurin korkki , joka: $G=(V,E)$ $V=\{1,\dots ,n\}$ $\mu (G)$ ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)))$

(M1) mille tahansa , jossa : , jos i ja j ovat vierekkäin, ja , muuten $i, j$ $i\neq j$ $M_{i,j}<0$ $M_{i,j}=0$
(M2) M :llä on täsmälleen yksi kerrannaisarvon 1 ominaisarvo;
(M3) ei ole sellaista nollasta poikkeavaa matriisia , että , ja että aina tai . [2] [1] ${\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)))$ $MX=0$ $X_{i,j}=0$ $i=j$ $M_{i,j}\neq 0$

Tunnettujen kaavioryhmien luokittelu

Colin de Verdièren invariantin näkökulmasta joillakin tunnetuilla graafiperheillä on tunnusomaisia piirteitä:

$\mu (K_{1})=0$ , , klo ; [1] [2] $\mu (K_{n})=n-1$ $\mu ({\overline {K_{n))})=1$ $n>1$
μ ≤ 1 jos ja vain jos G on lineaarinen metsä (metsä, jossa jokainen komponentti on polku, eli minkä tahansa kärjen esiintyvyys on enintään 2); [1] [3]
μ ≤ 2 jos ja vain jos G on ulompi tasograafi (kaikki kärjet ovat samalla pinnalla); [1] [2]
μ ≤ 3 jos ja vain jos G on tasograafi ; [1] [2]
μ ≤ 4 jos ja vain jos G on epäkoherentisti upotettava , eli G : ssä ei ole kahta sykliä, joille euklidiseen avaruuteen kartoitettuna (linkityskerroin) on nolla. [1] [4]

Samat kaavioryhmät osoittavat ominaispiirteensä analysoitaessa kaavion invariantin ja tämän kaavion komplementin välistä suhdetta:

Jos n -pisteisen graafin komplementti on lineaarinen metsä, niin μ ≥ n − 3 ; [1] [5]
Jos n -pisteisen graafin komplementti on ulompi tasograafi, niin μ ≥ n − 4 ; [1] [5]
Jos n pisteen graafin komplementti on tasograafi, niin μ ≥ n − 5 . [1] [5]

Laske alaikäiset

Graafin G molli on graafi H , joka on saatu G :stä poistamalla peräkkäisiä pisteitä, poistamalla reunoja ja supistämällä reunoja. Colin de Verdièren invariantti on monotoninen mollin ottamisessa siinä mielessä, että graafin minorisointi ei voi lisätä sen invarianttia:

Jos H on G :n molli , niin . [2]

{\näyttötyyli \mu (H)\leq \mu (G)}

Robertson-Seymour-lauseen mukaan mille tahansa k :lle on olemassa H , äärellinen graafien joukko siten, että mille tahansa graafille, jonka invariantti on korkeintaan k , H :n graafit eivät voi olla vähäisiä. Paperi ( Colin de Verdière 1990 ) luettelee tällaisten alaikäisten joukot k ≤ 3 ; kun k = 4, kelpaamattomien alaikäisten joukko koostuu seitsemästä Petersen- määriteltäessä epäyhtenäisesti upotettava graafi graafina, jossa μ ≤ 4, eikä Petersen-kaavioita alaikäisinä. [neljä]

Suhde kromaattiseen numeroon

( Colin de Verdière 1990 ) ehdotti, että mikä tahansa graafi, jossa on de Verdièren invariantti μ, voidaan värjätä käyttämällä enintään μ + 1 väriä. Esimerkiksi lineaaristen metsien (jonka komponentit ovat kaksiosaisia kaavioita) invariantti on 1; ulkotason kuvaajien invariantti on 2 ja ne voidaan värjätä kolmella värillä; tasokaavioiden invariantti on 3 ja ne voidaan värjätä neljällä värillä .

Graafeille, joissa de Verdierin invariantti on enintään neljä, oletus on totta; ne ovat kaikki epäyhtenäisesti upotettavissa, ja se tosiasia, että ne ovat viisivärisiä, on seurausta Hadwigerin arvelujen todisteesta graafisille, joissa ei ole K 6 -tyypin alavärejä ( Robertson, Seymour & Thomas 1993 ).

Muut ominaisuudet

Jos graafin leikkauspisteiden lukumäärä on k , niin sen de Verdierin invariantti on enintään k + 3. Esimerkiksi Kuratowskin graafit K 5 ja K 3,3 voidaan kuvata yhdellä leikkauspisteellä ja invariantti niitä on enintään neljä. [2]

Muistiinpanot

↑ 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 ).
↑ Teoksessa ( Colin de Verdière 1990 ) tätä tapausta ei ole tarkasteltu nimenomaisesti, mutta se seuraa eksplisiittisesti sellaisten graafien analyysin tuloksista, joissa ei ole "kolmio" ja " kynsi " muotoisia molliarvoja.
↑ 1 2 ( Lovász & Schrijver 1998 ).
↑ 1 2 3 ( Kotlov, Lovász & Vempala 1997 ).

Linkit

Colin de Verdière, Y. (1990), Sur un nouvel invariant des graphes et un critère de planarité , Journal of Combinatorial Theory, Series B osa 50 (1): 11–21 , DOI 10.1016/0095-8956(90930)9093 -F . Kääntäjä Neil Calkin Colin de Verdièrenä, Y. (1993), On a new graph invariant and a criterior for planarity, Robertson, Neil & Seymour, Paul , Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors , voi. 147, Contemporary Mathematics, American Mathematical Society, s. 137-147 .
van der Holst, Hein; Lovász, László & Schrijver, Alexander (1999), Colin de Verdièren graafiparametri , Graph Theory and Combinatorial Biology (Balatonlelle, 1996) , voi. 7, Bolyai Soc. Matematiikka. Stud., Budapest: Janos Bolyai Math. Soc., s. 29–85 , < http://www.cs.elte.hu/~lovasz/colinsurv.ps > .
Kotlov, Andreas; Lovász , László & Vempala, Santosh (1997), The Colin de Verdiere numero- ja palloesitykset graafista , 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), Borsukin lause antipodaalisille linkeille ja linkkittömästi upotettavien graafien spektrinen karakterisointi , Proceedings of the American Mathematical Society, osa 126 (5): 1275–1285 , DOI 10.10090-9039 98-04244-0 .
Robertson, Neil ; Seymour, Paul & Thomas, Robin (1993), Hadwigerin olettamus K6-vapaista graafista , Combinatorica osa 13: 279-361, doi : 10.1007 /BF01202354 , < http://www.math.gatech.edu/~thomas /PAP/hadwiger.pdf > .