नेसर ग्राफ

For the Kneser neighborhood graph of unimodular lattices, see Niemeier lattice.

Kneser graph
The Kneser graph K(5, 2), isomorphic to the Petersen graph
Named after	Martin Kneser
Vertices	${\binom {n}{k}}$
Edges	${\frac {1}{2}}{\binom {n}{k}}{\binom {n-k}{k}}$
Chromatic number	${\begin{cases}n-2k+2&n\geq 2k\\1&n<2k\end{cases}}$
Properties	${\tbinom {n-k}{k}}$-regular arc-transitive
Notation	K(n, k), KGn,k.
Table of graphs and parameters

ग्राफ सिद्धांत में, केनेसर ग्राफ K(n, k) (वैकल्पिक रूप से KG_n,k) वह ग्राफ है जिसके कोने संयोजन के अनुरूप हैंk-तत्व के एक सेट का सबसेट n तत्व, और जहां दो कोने आसन्न हैं यदि और केवल यदि दो संगत असंयुक्त सेट हैं। केनेसर ग्राफ का नाम मार्टिन केनेसर के नाम पर रखा गया है, जिन्होंने पहली बार 1956 में उनकी जांच की थी।

उदाहरण

केसर ग्राफ O₄ = K(7, 3)

केनेसर ग्राफ K(n, 1) पर पूरा ग्राफ है n शिखर।

केनेसर ग्राफ K(n, 2) पूर्ण ग्राफ़ के लाइन ग्राफ़ का पूरक ग्राफ़ है n शिखर।

केनेसर ग्राफ K(2n − 1, n − 1) विषम ग्राफ है O_n; विशेष रूप से O₃ = K(5, 2) पीटरसन ग्राफ है (शीर्ष दायां आंकड़ा देखें)।

केनेसर ग्राफ O₄ = K(7, 3), दाईं ओर देखा गया।

गुण

बुनियादी गुण

केनेसर ग्राफ $K(n,k)$ है ${\tbinom {n}{k}}$ शिखर। प्रत्येक शीर्ष में ठीक है ${\tbinom {n-k}{k}}$ पड़ोसियों।

केनेसर ग्राफ शीर्ष-सकर्मक ग्राफ और सममित ग्राफ है। कब $k=2$, केनेसर ग्राफ मापदंडों के साथ एक दृढ़ता से नियमित ग्राफ है $({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})$. हालांकि, यह दृढ़ता से नियमित नहीं है कि कब $k>2$, क्योंकि असन्निकट शीर्षों के भिन्न-भिन्न युग्मों में समान पड़ोसियों की भिन्न-भिन्न संख्याएँ होती हैं, जो समुच्चयों के संगत युग्मों के प्रतिच्छेदन के आकार पर निर्भर करता है।

क्‍योंकि केनेसर ग्राफ़ नियमित ग्राफ ़ और बढ़त-सकर्मक ग्राफ|एज-ट्रांसिटिव होते हैं, उनका के-वर्टेक्स-कनेक्टेड ग्राफ उनकी डिग्री (ग्राफ़ थ्योरी) के बराबर होता है, को छोड़कर $K(2k,k)$ जो डिस्कनेक्ट हो गया है। अधिक सटीक, की कनेक्टिविटी $K(n,k)$ है ${\tbinom {n-k}{k}},$ प्रति शीर्ष पड़ोसियों की संख्या के समान।

रंगीन संख्या

जैसा Kneser (1956) अनुमानित, केनेसर ग्राफ की रंगीन संख्या $K(n,k)$ के लिए $n\geq 2k$ बिल्कुल सही है n − 2k + 2; उदाहरण के लिए, पीटरसन ग्राफ को किसी भी उचित रंग में तीन रंगों की आवश्यकता होती है। यह अनुमान कई तरह से सिद्ध हुआ।

• लेज़्लो लोवाज़ ने 1978 में सांस्थितिकीय विधियों का उपयोग करके इसे साबित किया, टोपोलॉजिकल कॉम्बिनेटरिक्स के क्षेत्र को जन्म दे रहा है।
• इसके तुरंत बाद इमरे बैरनी ने बोरसुक-उलम प्रमेय और डेविड गेल की एक लेम्मा का उपयोग करते हुए एक सरल प्रमाण दिया।
• जोशुआ ई. ग्रीन ने 2002 में उत्कृष्ट स्नातक अनुसंधान के लिए मॉर्गन पुरस्कार अपने और सरलीकृत लेकिन फिर भी सामयिक प्रमाण के लिए जीता।
• 2004 में, जिरी मैटौसेक (गणितज्ञ) | जिरी मैटौसेक ने विशुद्ध रूप से दहनशील प्रमाण पाया।

इसके विपरीत, इन रेखांकन की भिन्नात्मक वर्णिक संख्या है $n/k$. कब $n<2k$, $K(n,k)$ कोई किनारा नहीं है और इसकी रंगीन संख्या 1 है।

हैमिल्टनियन चक्र

केनेसर ग्राफ K(n, k) में हैमिल्टनियन चक्र शामिल है यदि

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

तब से

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

सभी के लिए रखता है $k$ यह स्थिति संतुष्ट है अगर

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

केनेसर ग्राफ K(n, k) में एक हैमिल्टनियन चक्र होता है यदि कोई गैर-ऋणात्मक पूर्णांक मौजूद है जैसे कि $n=2k+2^{a}$. विशेष रूप से, विषम ग्राफ O_n का एक हैमिल्टनियन चक्र है यदि n ≥ 4. पीटरसन ग्राफ के अपवाद के साथ, सभी केनेसर ग्राफ जुड़े हुए हैं K(n, k) साथ n ≤ 27 हैमिल्टनियन हैं।

क्लिक्स

कब n < 3k, केनेसर ग्राफ K(n, k) में कोई त्रिभुज नहीं है। अधिक आम तौर पर, कब n < ck इसमें आकार का क्लिक (ग्राफ सिद्धांत) नहीं है c, जबकि इसमें ऐसे गुट होते हैं जब n ≥ ck. इसके अलावा, हालांकि केनेसर ग्राफ में हमेशा लंबाई चार का चक्र (ग्राफ सिद्धांत) होता है n ≥ 2k + 2, के मूल्यों के लिए n के करीब 2k सबसे छोटे विषम चक्र की परिवर्तनशील लंबाई हो सकती है।

व्यास

कनेक्टेड केसर ग्राफ की दूरी (ग्राफ सिद्धांत)। K(n, k) है

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

स्पेक्ट्रम

केनेसर ग्राफ का ग्राफ स्पेक्ट्रम K(n, k) में k + 1 अलग-अलग eigenvalues ​​​​शामिल हैं:

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

इसके अतिरिक्त $\lambda _{j}$ बहुलता (गणित) के साथ होता है ${\tbinom {n}{j}}-{\tbinom {n}{j-1}}$ के लिए $j>0$ और $\lambda _{0}$ बहुलता 1 है।

स्वतंत्रता संख्या

एर्डोस-को-राडो प्रमेय बताता है कि केनेसर ग्राफ की स्वतंत्रता संख्या K(n, k) के लिए $n\geq 2k$ है

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

संबंधित रेखांकन

जॉनसन ग्राफ J(n, k) वह ग्राफ है जिसके शीर्ष हैं k-तत्व सबसेट एक n-तत्व सेट, जब वे एक में मिलते हैं तो दो शीर्ष आसन्न होते हैं (k − 1)-तत्व सेट। जॉनसन ग्राफ J(n, 2) केनेसर ग्राफ का पूरक ग्राफ है K(n, 2). जॉनसन ग्राफ जॉनसन योजना से निकटता से संबंधित हैं, दोनों का नाम सेल्मर एम। जॉनसन के नाम पर रखा गया है।

सामान्यीकृत केनेसर ग्राफ K(n, k, s) का वही शीर्ष सेट है जो केनेसर ग्राफ में है K(n, k), लेकिन दो शीर्षों को जोड़ता है जब भी वे उस सेट के अनुरूप होते हैं जो एक दूसरे को काटते हैं s या कम आइटम। इस प्रकार K(n, k, 0) = K(n, k).

द्विदलीय केनेसर ग्राफ H(n, k) के शीर्षों का समुच्चय है k और n − k के संग्रह से तैयार किए गए आइटम n तत्व। जब भी एक सेट दूसरे का उपसमुच्चय होता है तो दो कोने एक किनारे से जुड़े होते हैं। केनेसर ग्राफ की तरह यह डिग्री के साथ सकर्मक शीर्ष है ${\tbinom {n-k}{k}}.$ द्विदलीय केनेसर ग्राफ को द्विदलीय दोहरे आवरण के रूप में बनाया जा सकता है K(n, k) जिसमें कोई प्रत्येक शीर्ष की दो प्रतियाँ बनाता है और प्रत्येक किनारे को किनारों के जोड़े से जोड़कर किनारों के जोड़े से बदल देता है। द्विदलीय केनेसर ग्राफ H(5, 2) Desargues ग्राफ और द्विदलीय Kneser ग्राफ है H(n, 1) एक क्राउन ग्राफ है।

संदर्भ

उद्धृत कार्य

• Bárány, Imre (1978), "A short proof of Kneser's conjecture", Journal of Combinatorial Theory, Series A, 25 (3): 325–326, doi:10.1016/0097-3165(78)90023-7, MR 0514626
• Chen, Ya-Chen (2003), "Triangle-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 generalised 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, p. 43, ISBN 9781107128446

• Greene, Joshua E. (2002), "A new short proof of Kneser's conjecture", American Mathematical Monthly, 109 (10): 918–920, doi:10.2307/3072460, JSTOR 3072460, MR 1941810
• 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)90022-5, hdl:10338.dmlcz/126050, MR 0514625
• Matoušek, Jiří (2004), "A combinatorial proof of Kneser's conjecture", Combinatorica, 24 (1): 163–170, doi:10.1007/s00493-004-0011-1, hdl:20.500.11850/50671, MR 2057690, 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.12406, MR 3826304
• Shields, Ian Beaumont (2004), Hamilton Cycle Heuristics in Hard Graphs, Ph.D. thesis, North Carolina State University, archived from the original on 2006-09-17, retrieved 2006-10-01
• Simpson, J. E. (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, pp. 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

बाहरी संबंध

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