ตัวอย่างการตอบโต้มากมายสำหรับการคาดเดาของแนช - วิลเลียมส์เกี่ยวกับความผิดพลาด?
คำถามจากปี 2013ให้ตัวอย่างการคาดเดาของแนช - วิลเลียมส์เกี่ยวกับความไม่สมบูรณ์ของดิจิกราฟที่หนาแน่น
ต่อมาเราพบตัวอย่างจำนวนนับสิบบนจุดยอดมากกว่า 30 จุดและเชื่อว่ามีตัวอย่างจำนวนนับไม่ถ้วน
กำหนด $K_{x_1,x_2,...x_n}$ ไปยัง digraph หลายส่วนที่สมบูรณ์พร้อมพาร์ติชัน $x_i$และขอบทุกด้านมีทิศทางทั้งสองทิศทาง ปล่อย$L=\max x_i$.
การคาดเดา 1: เป็น $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)$.
เพิ่มตัวอย่างการตอบโต้ที่แนะนำไม่ถูกต้องและเป็นผลมาจากข้อบกพร่องของโปรแกรม
คำตอบ
ตัวอย่างเหล่านี้คือกราฟสมมาตรนั่นคือกราฟ สำหรับกราฟการคาดเดาของแนช - วิลเลียมส์กลายเป็นทฤษฎีบทของ Chvatal (If$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$มีวงจรแฮมิลตัน) กล่าวอีกนัยหนึ่งตัวอย่างเหล่านี้ไม่สามารถเป็นตัวอย่างที่ใช้แทนการคาดเดาของ Nash-Williams ได้
แน่นอนว่าไม่มีวัฏจักรของแฮมิลตันในตัวอย่างเหล่านี้เนื่องจากมีชุดอิสระที่ใหญ่กว่า $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$.