Kneser graf

För Kneser grannskapsdiagram av unimodulära gitter, se Niemeier gitter .

Kneser-grafen
Kneser-grafen K (5, 2) , isomorf till Petersen-grafen
Döpt efter	Martin Kneser
Vertices	${\binom {n}{k}}$
Kanter	${\frac {1}{2}}{\binom {n}{k}}{\binom {nk}{k}}$
Kromatiskt nummer	${\begin{cases}n-2k+2&n\geq 2k\\1&n<2k\end{cases}}$
Egenskaper	${\tbinom {nk}{k}}$ -regular arc-transitive
Notation	K ( n , k ) , k , KGn .
Tabell över grafer och parametrar

I grafteorin är Kneser -grafen K ( n , k ) (alternativt KG _{n , k} ) den graf vars hörn motsvarar delmängderna k -element av en uppsättning av n element , och där två hörn ligger intill om och endast om två motsvarande uppsättningar är osammanhängande . Kneser-grafer är uppkallade efter Martin Kneser , som först undersökte dem 1956.

Exempel

Kneser-graf O ₄ = K (7, 3)

Kneser-grafen K ( n , 1) är den fullständiga grafen på n hörn.

Kneser-grafen K ( n , 2) är komplementet till linjegrafen för hela grafen på n hörn.

Kneser-grafen K (2 n − 1, n − 1) är den udda grafen O _n ; i synnerhet O ₃ = K (5, 2) är Petersen-grafen (se bilden uppe till höger).

Kneser-grafen O ₄ = K (7, 3) , visualiserad till höger.

Egenskaper

Grundläggande egenskaper

Knesergrafen $K(n,k)$ har ${\tbinom {n}{k}}$ hörn. Varje vertex har exakt ${\tbinom {nk}{k}}$ grannar.

Kneser-grafen är vertextransitiv och bågtransitiv . När $k=2$ är Kneser-grafen en starkt regelbunden graf med parametrar $({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{ 2}})$ . Det är dock inte starkt regelbundet när $k>2$ , eftersom olika par av icke-angränsande hörn har olika antal gemensamma grannar beroende på storleken på skärningspunkten mellan motsvarande par av uppsättningar.

Eftersom Kneser-grafer är regelbundna och kanttransitiva , är deras vertexanslutning lika med deras grad , förutom $K(2k,k)$ som är frånkopplad. Mer exakt är anslutningsmöjligheten för $K(n,k)$${\tbinom {nk}{k}},$ samma som talet av grannar per vertex.

Kromatiskt nummer

Som Kneser ( 1956 ) antog är det kromatiska talet för Kneser-grafen $K(n,k)$ för $n\geq 2k$ exakt n − 2 k + 2 ; Petersen-grafen kräver till exempel tre färger i valfri färg. Denna gissning bevisades på flera sätt.

• László Lovász bevisade detta 1978 med topologiska metoder, vilket gav upphov till området topologisk kombinatorik .
• Strax därefter gav Imre Bárány ett enkelt bevis, med hjälp av Borsuk-Ulam-satsen och ett lemma av David Gale .
• Joshua E. Greene vann 2002 Morgan-priset för enastående forskning på grundnivå för hans ytterligare förenklade men fortfarande topologiska bevis.
• År 2004 hittade Jiří Matoušek ett rent kombinatoriskt bevis .

Däremot är det kromatiska bråktalet för dessa grafer $n/k$ . När $n<2k$ , har $K(n,k)$ inga kanter och dess kromatiska tal är 1.

Hamiltonsk cykel

Kneser-grafen K ( n , k ) innehåller en Hamiltonsk cykel if

$$n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).$$

Eftersom

$${\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1$$

gäller för alla $k$ detta villkor är uppfyllt om

$$n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1 \ungefär 2,62k+1.$$

Kneser-grafen K ( n , k ) innehåller en Hamiltonsk cykel om det finns ett icke-negativt heltal a så att $n=2k+2^{a}$ . I synnerhet har den udda grafen O _n en Hamiltonsk cykel om n ≥ 4 . Med undantag för Petersen-grafen är alla sammankopplade Kneser-grafer K ( n , k ) med n ≤ 27 Hamiltonska.

Klickor

När n < 3 k innehåller Kneser-grafen K ( n , k ) inga trianglar. Mer allmänt, när n < ck innehåller det inte klicker av storlek c , medan det innehåller sådana klicker när n ≥ ck . Dessutom, även om Kneser-grafen alltid innehåller cykler med längd fyra närhelst n ≥ 2 k + 2 , för värden på n nära 2 k kan den kortaste udda cykeln ha variabel längd.

Diameter

Diametern på en sammankopplad Kneser- graf K ( n k ) , är

$$\left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.$$

Spektrum

Spektrum för Kneser - grafen K ( n : k ) , består av k + 1 distinkta egenvärden

$$\lambda _{j}=(-1)^{j}{\binom {nkj}{kj}},\qquad j=0,\ldots ,k.$$

Dessutom förekommer $\lambda _{j}$ med multiplicitet ${\tbinom {n}{j}}-{\tbinom {n}{j- 1}}$ för $j>0$ och $\lambda _{0}$ har multipliciteten 1.

Independence nummer

Erdős –Ko–Rado-satsen säger att oberoendetalet för Kneser-grafen K ( n , k ) för $n\geq 2k$ är

$$\alpha (K(n,k))={\binom {n-1}{k-1}}.$$

Relaterade grafer

Johnson -grafen J ( n , k ) är grafen vars hörn är delmängderna k -element av en n -elementmängd, två hörn ligger intill varandra när de möts i en ( k − 1) -elementmängd. Johnson-grafen J ( n , 2) är komplementet till Kneser-grafen K ( n , 2) . Johnson-grafer är nära besläktade med Johnson-schemat , som båda är uppkallade efter Selmer M. Johnson .

Den generaliserade Kneser-grafen K ( n , k , s ) har samma vertexuppsättning som Kneser-grafen K ( n , k ) , men kopplar samman två hörn närhelst de motsvarar mängder som skär varandra i s eller färre objekt. Således K ( n , k , 0) = K ( n , k ) .

Den tvådelade Kneser-grafen H ( n , k ) har som hörn uppsättningarna av k och n − k objekt dragna från en samling av n element. Två hörn är förbundna med en kant när en mängd är en delmängd av den andra. Liksom Kneser-grafen är den vertex transitiv med grad ${\tbinom {nk}{k}}.$ Den tvådelade Kneser-grafen kan bildas som ett tvådelat dubbelt omslag av K ( n , k ) där man gör två kopior av varje vertex och ersätter varje kant med ett par av kanter som förbinder motsvarande par av hörn. Den tvådelade Kneser-grafen H (5, 2) är Desargues-grafen och den tvådelade Kneser-grafen H ( n , 1) är en krongraf .

Anförda verk

•   Bárány, Imre (1978), "A short proof of Knesers conjecture", Journal of Combinatorial Theory , Series A, 25 (3): 325–326, doi : 10.1016/0097-3165(78)90023-7 , MR 62651
•   Chen, Ya-Chen (2003), "Triangel-free Hamiltonian Kneser graphs", Journal of Combinatorial Theory , Series B, 89 (1): 1–16, doi : 10.1016/S0095-8956(03)00040-6 , MR 1999733
•   Denley, Tristan (1997), "The odd girth of the generalized Kneser graph", European Journal of Combinatorics , 18 (6): 607–611, doi : 10.1006/eujc.1996.0122 , MR 1468332
•   Godsil, Christopher ; Meagher, Karen (2015), Erdős–Ko–Rado Theorems: Algebraic Approaches , Cambridge Studies in Advanced Mathematics, Cambridge University Press, sid. 43, ISBN 9781107128446

•    Greene, Joshua E. (2002), "A new short proof of Knesers conjecture", American Mathematical Monthly , 109 (10): 918–920, doi : 10.2307/3072460 , JSTOR 3072460 , MR 194180
• Kneser, Martin (1956), "Aufgabe 360", Jahresbericht der Deutschen Mathematiker-Vereinigung , 58 (2): 27
•   Lovász, László (1978), "Kneser's conjecture, chromatic number, and homotopy", Journal of Combinatorial Theory , Series A, 25 (3): 319–324, doi : 10.1016/0097-3165(78) 59002 hdl . : 10338.dmlcz/126050 , MR 0514625
•    Matoušek, Jiří (2004), "A combinatorial proof of Knesers conjecture", Combinatorica , 24 ( 1 ): 163–170, doi : 10.1007 / s00493-004-0011-1 , hdl : 5118500/9 , S2CID 42583803
•   Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2021), "Sparse Kneser graphs are Hamiltonian", Journal of the London Mathematical Society , New York, 103 (4): 912–919, arXiv : 1711.01636 , doi : 10.1112/jlms.12408 , 3MR 408 , 3MR 408
• Shields, Ian Beaumont (2004), Hamilton Cycle Heuristics in Hard Graphs , Ph.D. avhandling, North Carolina State University , arkiverad från originalet 2006-09-17 , hämtad 2006-10-01
•   Simpson, JE (1991), "Hamiltonian bipartite graphs", Proceedings of the Twenty-Second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991) , Congressus Numerantium, vol. 85, s. 97–110, MR 1152123
•   Valencia-Pabon, Mario; Vera, Juan-Carlos (2005), "On the diameter of Kneser graphs", Discrete Mathematics , 305 (1–3): 383–385, doi : 10.1016/j.disc.2005.10.001 , MR 2186709
•   Watkins, Mark E. (1970), "Connectivity of transitive graphs", Journal of Combinatorial Theory , 8 : 23–29, doi : 10.1016/S0021-9800(70)80005-9 , MR 0266804

externa länkar

• Weisstein, Eric W. "Kneser Graph" . MathWorld .
• Weisstein, Eric W. "Odd Graph" . MathWorld .