Colin de Verdier invariantní

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. ledna 2018; kontroly vyžadují 7 úprav .

Colin de Verdière invariant je charakteristika grafu definovaného pro jakýkoli graf G , který představil Yves Colin de Verdière v roce 1990 v procesu studia násobnosti druhé vlastní hodnoty některých Schrödingerových operátorů . [jeden] $\mu (G)$

Definice

Nechť je jednoduchý (neobsahující smyčky a více hran) acyklický graf. Bez ztráty obecnosti pojmenujme množinu vrcholů takto: . Pak je největší korek jakékoli matice takový, že: $G=(V,E)$ $V=\{1,\tečky ,n\}$ $\mu (G)$ ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)))$

(M1) pro libovolnou , kde : , pokud i a j sousedí, a , jinak $i,j$ $i\neq j$ $M_{i,j}<0$ $M_{i,j}=0$
(M2) M má právě jednu vlastní hodnotu násobnosti 1;
(M3) neexistuje taková nenulová matice jako , a to kdykoliv nebo . [2] [1] ${\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)))$ $MX=0$ $X_{i,j}=0$ $i=j$ $M_{i,j}\neq 0$

Klasifikace známých skupin grafů

Z hlediska Colin de Verdière invariantu mají některé známé rodiny grafů charakteristické rysy:

$\mu (K_{1})=0$ , , v ; [1] [2] $\mu (K_{n})=n-1$ $\mu ({\overline {K_{n))})=1$ $n>1$
μ ≤ 1 právě tehdy, když G je lineární les (les, ve kterém je každá složka cestou, to znamená, že výskyt jakéhokoli vrcholu je nejvýše 2); [1] [3]
μ ≤ 2 právě tehdy, když G je vnějši rovinný graf (všechny vrcholy leží na stejné ploše); [1] [2]
μ ≤ 3 právě tehdy, když G je rovinný graf ; [1] [2]
μ ≤ 4 právě tehdy, když je G nekoherentně vnořitelné , tj. v G neexistují dva cykly , pro které je při mapování do euklidovského prostoru (spojovací koeficient) nula. [1] [4]

Stejné skupiny grafů ukazují své charakteristické rysy při analýze vztahu mezi invariantem grafu a doplňkem tohoto grafu:

Je-li doplňkem grafu s n vrcholy lineární les, pak μ ≥ n − 3 ; [1] [5]
Je-li doplňkem grafu s n vrcholy vnější rovinný graf, pak μ ≥ n − 4 ; [1] [5]
Je-li doplňkem grafu s n vrcholy rovinný graf, pak μ ≥ n − 5 . [1] [5]

Počítat nezletilé

Menší část grafu G je graf H získaný z G postupným odstraňováním vrcholů, odstraňováním hran a kontrakcí hran. Colin de Verdièreův invariant je monotónní při použití moll v tom smyslu, že minorizace grafu nemůže zvýšit jeho invariant:

Je-li H menší než G , pak . [2]

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

Podle Robertson-Seymourova teorému pro nějaké k existuje H , konečná množina grafů taková, že pro jakýkoli graf s invariantem nanejvýš k nemohou být grafy z H menší. Práce ( Colin de Verdière 1990 ) uvádí množiny takových invalidních nezletilých pro k ≤ 3; pro k = 4 se množina neplatných nezletilých osob skládá ze sedmi grafů Petersenovy rodiny podle definice disjunktně vnořitelného grafu jako grafu s μ ≤ 4 a žádných Petersenových grafů jako nezletilých. [čtyři]

Vztah s chromatickým číslem

( Colin de Verdière 1990 ) navrhli, že jakýkoli graf s de Verdièrovým invariantem μ lze obarvit pomocí nejvýše μ + 1 barev. Například lineární lesy (jejichž složkami jsou bipartitní grafy) mají invariant 1; vnější rovinné grafy mají invariant 2 a lze je obarvit třemi barvami; rovinné grafy mají invariant 3 a lze je vybarvit čtyřmi barvami .

Pro grafy s de Verdierovým invariantem nejvýše čtyři je předpoklad pravdivý; všechny jsou nekoherentně vnořitelné a skutečnost, že jsou pětibarevné, je důsledkem důkazu Hadwigerovy domněnky pro grafy bez minorů typu K 6 in ( Robertson, Seymour & Thomas 1993 ).

Další vlastnosti

Pokud je počet průsečíků grafu k , pak de Verdierův invariant pro něj bude nejvýše k + 3. Například Kuratowského grafy K 5 a K 3,3 lze zobrazit s jedním průsečíkem a invariant pro budou maximálně čtyři. [2]

Poznámky

↑ 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 ).
↑ V ( Colin de Verdière 1990 ) se tento případ výslovně neuvažuje, ale výslovně vyplývá z výsledků analýzy grafů, které nemají minory ve tvaru „trojúhelník“ a „ dráp “.
↑ 1 2 ( Lovász & Schrijver 1998 ).
↑ 1 2 3 ( Kotlov, Lovász & Vempala 1997 ).

Odkazy

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(930)900 -F _ Přeložil Neil Calkin jako Colin de Verdière, Y. (1993), O novém invariantu grafu a kritériu rovinnosti, v Robertson, Neil & Seymour, Paul , Graph Structure Theory: Proc. Společná letní výzkumná konference AMS–IMS–SIAM o Graph Minors , sv. 147, Současná matematika, Americká matematická společnost, s. 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) , sv. 7, Bolyai Soc. Matematika. Stud., Budapešť: Janos Bolyai Math. Soc., str. 29–85 , < http://www.cs.elte.hu/~lovasz/colinsurv.ps > .
Kotlov, Ondřej; 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 teorem for antipodal links and a spectral characterisation of linklessly embeddable graphs , Proceedings of the American Mathematical Society vol . 126 (5): 1275–1285 , DOI 309-S09 10.1 98-04244-0 .
Robertson, Neil ; Seymour, Paul & Thomas, Robin (1993), Hadwiger's conjecture for K6 - free graphs , Combinatorica vol. 13: 279–361, doi : 10.1007/BF01202354 , < http://www.math.gatech.edu/~thomas /PAP/hadwiger.pdf > .