हैमिल्टनिटी के बारे में नैश-विलियम्स के अनुमान के लिए बहुत सारे प्रतिवाद हैं?
2013 से प्रश्न नैश-विलियम्स के घने डिगलों की हैमिल्टनिटी के बारे में एक प्रतिवाद देता है।
बाद में, हमने 30 से अधिक शीर्षों पर दसियों प्रतिरूपों को पाया और माना कि असीम रूप से कई प्रतिपक्ष हैं।
परिभाषित करें $K_{x_1,x_2,...x_n}$ विभाजन के साथ पूर्ण मल्टीपार्टेट डिग्राफ $x_i$और हर किनारा दोनों दिशाओं में उन्मुख है। चलो$L=\max x_i$।
अनुमान 1: as $n,L$ अलग-अलग हैं, असीम रूप से कई प्रतिपक्ष हैं
Q1 क्या यह असीम रूप से कई प्रतिपक्ष देता है?
के लिए sagemath कोड $K_{1,1,2,5}$:
G1=graphs.CompleteMultipartiteGraph((1,1,2,5)).to_directed()
sage: print G1.edges(False)
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 0), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 0), (4, 1), (4, 2), (4, 3), (5, 0), (5, 1), (5, 2), (5, 3), (6, 0), (6, 1), (6, 2), (6, 3), (7, 0), (7, 1), (7, 2), (7, 3), (8, 0), (8, 1), (8, 2), (8, 3)]
15 शीर्षकों पर जवाबी कार्रवाई के लिए $x_i=(1, 1, 1, 2, 2, 8)$।
जोड़ा गया सुझाव दिया गया है कि गलतियां गलत हैं और प्रोग्राम बग का परिणाम हैं।
जवाब
ये उदाहरण सममित डिग्रियां हैं, अर्थात रेखांकन। रेखांकन के लिए, नैश-विलियम्स अनुमान सिर्फ च्वाटल का प्रमेय बन जाता है (यदि$G$ एक ग्राफ है $n\geq 3$ डिग्री अनुक्रम के साथ कोने $d_1\leq d_2\leq \dots\leq d_n$ और सभी के लिए $1\leq i<n/2$, $d_i\geq i+1$ या $d_{n-i}\geq n-i$, तब फिर $G$एक हैमिल्टनियन चक्र है)। दूसरे शब्दों में, इन उदाहरणों को नैश-विलियम्स अनुमान के प्रतिपक्ष नहीं किया जा सकता है।
इन उदाहरणों में निश्चित रूप से कोई हैमिल्टन चक्र नहीं है क्योंकि एक स्वतंत्र सेट इससे बड़ा है $n/2$, लेकिन नैश-विलियम्स की शर्त पूरी नहीं हुई। उदाहरण देखें$K_{1,1,1,1,5}$मिसाल के तौर पर; दोनों डिग्री सीक्वेंस हैं$[4,4,4,4,4,8,8,8,8]$, लेकिन आ $d_4=4$ तथा $d_{9-4}=d_5=4$।