Graph Puzzles II.1: Counterexamples to Jain's Second Unit Vector Flows Conjecture

यहाँ निकोले यूल्यानोव के शोध पत्र "Counterexamples to Jain's second unit vector flows conjecture" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र K. जैन द्वारा ग्राफ पर यूनिट वेक्टर फ्लो (unit vector flows) और टट के 5-फ्लो अनुमान (Tutte's 5-flow conjecture) के साथ उनके संबंध के संबंध में प्रस्तावित दो परस्पर जुड़े हुए अनुमानों (conjectures) को संबोधित करता है।

• अनुमान 1.1 (यूनिट वेक्टर फ्लो): प्रत्येक ब्रिजलेस (bridgeless) ग्राफ में एक ऐसा फ्लो होता है जहाँ प्रत्येक किनारे (edge) को 2-आयामी इकाई गोले $S^2$ से एक वेक्टर सौंपा जाता है (एक nowhere-zero 3-आयामी फ्लो)।
• अनुमान 1.2 ($S^2$ nz5-flow): एक मैपिंग $q: S^2 \to \{-4, -3, -2, -1, 1, 2, 3, 4\}$ मौजूद है जिससे:
  1. प्रतिच्छेदी बिंदु शून्य के योग के बराबर होते हैं ($q(-x) = -q(x)$)।
  2. एक महान वृत्त (great circle) पर समान दूरी पर स्थित कोई भी तीन बिंदु शून्य के योग के बराबर होते हैं ($q(a) + q(b) + q(c) = 0$)।
• निहितार्थ (The Implication): यदि अनुमान 1.1 और 1.2 दोनों सत्य हैं, तो वे संयुक्त रूप से टट के 5-फ्लो अनुमान (कि प्रत्येक ब्रिजलेस क्यूबिक ग्राफ में एक nowhere-zero 5-flow होता है) को सिद्ध करेंगे।

इस शोध पत्र का विशिष्ट ध्यान अनुमान 1.2 को गलत सिद्ध करने पर है, यह दिखाते हुए कि $S^2$ के कुछ परिमित उपसमुच्चयों (finite subsets) के लिए ऐसा मैपिंग मौजूद नहीं है। विशेष रूप से, लेखक दिखाते हैं कि कुछ विन्यासों (configurations) के लिए, बाधाएं $\pm 5$ के मानों का उपयोग करने के लिए मजबूर करती हैं, जिसका अर्थ है कि एक nowhere-zero 6-flow की आवश्यकता है, और एक nowhere-zero 5-flow असंभव है।

2. कार्यप्रणाली (Methodology)

लेखक ज्यामितीय निर्माण (geometric construction) और बूलियन संतुष्टिता (Boolean Satisfiability - SAT) समाधान के माध्यम से कम्प्यूटेशनल सत्यापन के संयोजन का उपयोग करते हैं।

A. ज्यामितीय निर्माण (Geometric Construction)

लेखक इकाई गोले $S^2$ पर बिंदुओं के परिमित उपसमुच्चय का निर्माण करते हैं जिन्हें "महान-वृत्त त्रिकों" (great-circle triples - एक महान वृत्त पर तीन समान दूरी वाले बिंदु) की बाधाओं को अधिकतम करने के लिए डिज़ाइन किया गया है।

1. प्रति-उदाहरण 1 (50-बिंदु सेट):

   • Icosidodecahedron (30 बिंदु) पर आधारित।
   • निर्माण इकोसिडोडेकाहेड्रोन का विस्तार करता है, जिसमें प्रत्येक शीर्ष (vertex) के चारों ओर छोटे वृत्त रखे जाते हैं और उन्हें विशिष्ट गोलाकार दूरियों ($2\pi/5$) के आधार पर प्रतिच्छेदित किया जाता है।
   • इसके परिणामस्वरूप 50 बिंदुओं का एक सेट प्राप्त होता है जिसमें 40 महान-वृत्त त्रिक होते हैं।
   • निर्देशांकों में गोल्डन रेशियो $\phi$ और विशिष्ट बीजगणितीय स्केलिंग कारक शामिल हैं।
   • टोपोलॉजिकल रूप से, यह संरचना पीटर्सन ग्राफ (Petersen graph) और एक मोबियस लैडर (Möbius ladder) से संबंधित है।

2. प्रति-उदाहरण 2 (36-बिंदु सेट):

   • वर्गमूल अंकगणित (Square root arithmetic) पर आधारित।
   • निर्देशांक $\sqrt{1}$ और $\sqrt{3}$ के रैखिक संयोजनों का उपयोग करके उत्पन्न किए गए हैं, जिन्हें इकाई गोले पर सामान्यीकृत (normalized) किया गया है।
   • लेखक एक बड़ा संभावित सेट उत्पन्न करते हैं, उन बिंदुओं को पुनरावृत्ति से हटाते हैं जो कई त्रिकों में भाग नहीं लेते हैं, और 36 बिंदुओं और 13 त्रिकों के एक न्यूनतम जुड़ा हुआ घटक (minimal connected component) पर अभिसरित होते हैं।

B. कम्प्यूटेशनल सत्यापन (SAT Solving)

यह सिद्ध करने के लिए कि इन सेटों के लिए केवल $\{-4, \dots, 4\}$ मानों का उपयोग करके कोई वैध लेबलिंग मौजूद नहीं है:

• एन्कोडिंग (Encoding): समस्या को एक बूलियन संतुष्टिता (Boolean Satisfiability - SAT) उदाहरण के रूप में एनकोड किया गया है।
  • चर (Variables) प्रत्येक बिंदु को $\{-4, \dots, 4\}$ के असाइनमेंट का प्रतिनिधित्व करते हैं।
  • बाधाओं में शामिल हैं:
    • Exactly-one: प्रत्येक बिंदु को ठीक एक मान मिलता है।
    • Antipodal: $q(-p) = -q(p)$।
    • Triple-sum: प्रत्येक महान-वृत्त त्रिक के लिए $q(a) + q(b) + q(c) = 0$।
• सॉल्वर (Solvers): परिणामी CNF सूत्रों को PicoSAT और pycosat में फीड किया गया था।
• औपचारिक सत्यापन (Formal Verification): गणितीय कठोरता सुनिश्चित करने के लिए परिणामों को bv_decide टैक्टिक के साथ Lean 4 का उपयोग करके क्रॉस-वैलिडेट किया गया था।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

अनुमान 1.2 का खंडन (Disproof of Conjecture 1.2)

शोध पत्र जैन के दूसरे अनुमान के दो निश्चित प्रति-उदाहरण प्रदान करता है:

1. 50-बिंदु Icosidodecahedron विस्तार:

   • SAT सॉल्वर ने निर्धारित किया कि CNF सूत्र (200 चर, 19,765 क्लॉज) असंतोषजनक (unsatisfiable) है।
   • यह सिद्ध करता है कि केवल $\{\pm 1, \dots, \pm 4\}$ का उपयोग करके कोई लेबलिंग मौजूद नहीं है।
   • एक वैध लेबलिंग मौजूद है यदि रेंज को $\{\pm 1, \dots, \pm 4\}$ से बढ़ाकर $\{\pm 1, \dots, \pm 5\}$ कर दिया जाए (एक nowhere-zero 6-flow)।

2. 36-बिंदु वर्गमूल निर्माण:

   • SAT सॉल्वर ने निर्धारित किया कि CNF सूत्र (144 चर, 6,710 क्लॉज) असंतोषजनक (unsatisfiable) है।
   • पहले उदाहरण की तरह, इस सेट को बाधाओं को संतुष्ट करने के लिए $\pm 5$ मानों की आवश्यकता होती है।
   • रेंज $\{\pm 1, \dots, \pm 5\}$ के लिए एक वैध लेबलिंग मौजूद है।

संरचनात्मक अंतर्दृष्टि (Structural Insights)

• शोध पत्र फ्लो बाधाओं के संदर्भ में Icosidodecahedron, Petersen graph, और Möbius ladder के बीच के संबंध को स्पष्ट करता है।
• यह दर्शाता है कि जबकि पीटर्सन ग्राफ एक nowhere-zero 5-flow (पूर्णांक मान) स्वीकार करता है, गोले पर इसके शीर्षों का ज्यामितीय निरूपण (विशिष्ट "महान वृत्त" बाधाओं के साथ) विशिष्ट बीजगणितीय संरचना के कारण उच्च फ्लो संख्या (6-flow) को मजबूर करता है।

4. महत्व और भविष्य की दिशाएँ (Significance and Future Directions)

• टट के अनुमान पर प्रभाव (Impact on Tutte's Conjecture): चूंकि अनुमान 1.2 गलत है, इसलिए जैन के दोनों अनुमानों को मिलाकर टट के 5-फ्लो अनुमान को सिद्ध करने का विशिष्ट मार्ग टूट गया है। शोध पत्र सुझाव देता है कि टट के अनुमान के लिए प्रमाण रणनीति को बचाने के लिए $S^2$ के एक अलग उपसमुच्चय (संभवतः अनंत या विशिष्ट बीजगणितीय गुणों वाले) की आवश्यकता हो सकती है।
• Flow बनाम Mod-k Flow: लेखक एक अनुभवजन्य अवलोकन नोट करते हैं कि परीक्षण किए गए उपसमुच्चयों के लिए, न्यूनतम $k$ जो एक nowhere-zero $k$-flow के लिए आवश्यक है, वह nowhere-zero mod-$k$ flow के समान ही है। शोध पत्र प्रश्न उठाता है कि क्या यह समानता सार्वभौमिक रूप से लागू होती है।
• खुले प्रश्न (Open Questions):
  • क्या ऐसा उपसमुच्चय पाया जा सकता है जिसे $\pm 6$ या उच्चतर मानों की आवश्यकता हो?
  • प्रति-उदाहरण सेट का न्यूनतम आकार क्या है?
  • क्या एक "अच्छा" उपसमुच्चय (जैसे, बीजगणितीय निर्देशांकों वाला) मिल सकता है जो टट के अनुमान का समर्थन करने के लिए 5-flow स्वीकार करता हो?

निष्कर्ष (Conclusion)

निकोले यूल्यानोव ने दो प्रति-उदाहरणों का निर्माण करके जैन के दूसरे अनुमान को सफलतापूर्वक गलत सिद्ध किया है, जहाँ महान-वृत्त त्रिकों की ज्यामितीय बाधाएं nowhere-zero 5-flow को असंभव बना देती हैं। यह कार्य परिष्कृत ज्यामितीय निर्माण और कठोर SAT-आधारित सत्यापन पर निर्भर करता है, जो शोध के केंद्र को वैकल्पिक ज्यामितीय संरचनाओं की खोज की ओर स्थानांतरित करता है जो अभी भी टट के 5-फ्लो अनुमान का समर्थन कर सकती हैं।