एक एआई ने 1990 के दशक का रंग-अनुमान डुबो दिया

रेखाओं से जुड़े बिंदुओं का एक जाल लीजिए — एक ग्राफ़। संपूर्ण रंगाई (टोटल कलरिंग) हर बिंदु और हर रेखा को एक रंग देती है, तीन नियमों का पालन करते हुए: दो पड़ोसी बिंदुओं के रंग अलग हों, एक बिंदु पर मिलने वाली दो रेखाओं के रंग अलग हों, और किसी रेखा का रंग उसके दोनों सिरों के बिंदुओं से अलग हो। जितने कम से कम रंगों से यह संभव हो, उस संख्या को संपूर्ण वर्णिक संख्या (टोटल क्रोमैटिक नंबर) कहते हैं, जिसे χ″(G) लिखा जाता है।

अब इसे कठिन बनाइए। हर बिंदु और हर रेखा को अनुमत रंगों की उसकी अपनी सूची दीजिए, सभी सूचियाँ एक ही आकार k की, और माँग कीजिए कि सूचियों से चुनकर एक मान्य रंगाई बने। सूचियाँ चाहे जो हों, जो सबसे छोटा k काम करता है, वह सूची संपूर्ण वर्णिक संख्या χ″ℓ(G) है। यह कभी χ″(G) से छोटी नहीं हो सकती: अगर सभी सूचियाँ एक जैसी हों, तो आप साधारण समस्या पर लौट आते हैं।

1990 के दशक के अंत का एक अनुमान

तीन समूहों — बोरोदिन, कोस्तोचका और वुडॉल; युवान, मोहार और श्क्रेकोव्स्की; हिल्टन और जॉनसन — ने 1990 के दशक के अंत में स्वतंत्र रूप से प्रस्ताव रखा कि निजी सूचियों की कभी कोई क़ीमत नहीं चुकानी पड़ती:

हर ग्राफ़ के लिए χ″ℓ(G) = χ″(G) (दो बिंदुओं के बीच कई रेखाएँ होने पर भी)।

यही सूची संपूर्ण रंगाई अनुमान (List Total Colouring Conjecture) है। साक्ष्य इसके पक्ष में थे: यह उन ग्राफ़ों के लिए सही है जिनमें किसी बिंदु पर दो से ज़्यादा रेखाएँ नहीं हैं, और यह ज्ञात था कि हर बिंदु पर ठीक तीन रेखाओं वाले हर ग्राफ़ (घनीय, यानी क्यूबिक ग्राफ़) को सूचियों से अधिकतम 5 रंग चाहिए।

प्रति-उदाहरण

कनाडा की यूनिवर्सिटी ऑफ़ विक्टोरिया के जोनाथन नोएल अब 20 बिंदुओं वाला एक घनीय ग्राफ़ दिखाते हैं जिसका χ″ = 4 है, पर χ″ℓ = 5। अनुमान ग़लत है।

निर्माण सुगठित है। K₂,₃ नाम के एक छोटे ग्राफ़ की चार प्रतियाँ लीजिए: दो “निजी” बिंदु, जिनमें से हर एक उन्हीं तीन “अंतिम” (टर्मिनल) बिंदुओं से जुड़ा है। फिर प्रतियों के हर जोड़े को टर्मिनलों के बीच ठीक एक “क्रॉस” रेखा से जोड़िए। अंत में हर बिंदु पर तीन रेखाएँ हो जाती हैं।

केवल चार रंगों वाली संपूर्ण रंगाई के साथ ग्राफ़ G, रंगों को आकृतियों और रेखा-शैलियों से दिखाया गया है। — चित्र 1, नोएल (2026), arXiv:2609.38417।

साधारण खेल में चार रंग काफ़ी हैं: रंग 4 सभी निजी बिंदुओं और सभी क्रॉस रेखाओं को जाता है, जो कभी एक-दूसरे को नहीं छूतीं, और एक छोटी तालिका तथा एक चक्रीय नियम बाक़ी काम सँभाल लेते हैं।

ऐसी सूचियाँ जिन्हें संतुष्ट नहीं किया जा सकता

जाल में 1 से 5 तक के रंग इस्तेमाल होते हैं। खंड i के हर बिंदु और हर रेखा को “i को छोड़कर सभी रंग” वाली सूची मिलती है; क्रॉस रेखाओं को सावधानी से चुनी गई ऐसी सूचियाँ मिलती हैं जिनमें 5 या i + 2 नहीं होता। फिर प्रमाण एक छोटी जासूसी कहानी की तरह चलता है:

• प्रमेयिका: K₂,₃ की किसी भी 4-रंगाई में दोनों निजी बिंदुओं का रंग एक ही होना चाहिए।
• इसलिए हर खंड i के पास रंगों का एक जोड़ा {i, sᵢ} होता है, और दो खंडों के बीच की हर क्रॉस रेखा को ऐसा रंग इस्तेमाल करना होगा जो दोनों जोड़ों में साझा हो।
• थोड़ी-सी गिनती से पता चलता है कि कोई एक रंग t चारों जोड़ों में होना चाहिए।
• t के हर संभव मान के लिए, कोई एक विशेष क्रॉस रेखा पाती है कि वह रंग उसकी सूची में नहीं है। विरोधाभास।

सूचियों का आवंटन: हर बिंदु और रेखा 1 से 5 तक का हर रंग इस्तेमाल कर सकती है, सिवाय दर्शाए गए रंग के। कोई भी संपूर्ण रंगाई इन सूचियों का पालन नहीं कर सकती। — चित्र 2, नोएल (2026), arXiv:2609.38417।

मशीन ने खोजा, गणितज्ञ ने जाँचा

शोध-पत्र अपनी उत्पत्ति के बारे में असामान्य रूप से स्पष्टवादी है। 24 सितंबर 2026 को नोएल ने ChatGPT 6 Astra Ultra को अनुमान ग़लत साबित करने का निर्देश दिया, और उसने “लेखक की ओर से बहुत कम इनपुट के साथ” प्रति-उदाहरण तैयार किया। उन्होंने तर्कों की जाँच की और मॉडल द्वारा बनाए मसौदों से पाठ दोबारा लिखा; मॉडल ने प्रूफ़ पढ़ने में भी मदद की, संदर्भ सुझाए और चित्र बनाए। घोषणा इस वाक्य पर ख़त्म होती है: “शुद्धता की पूरी ज़िम्मेदारी लेखक की है।” यह शोध-पत्र एक प्रीप्रिंट है, लेकिन प्रमाण इतना छोटा है कि धैर्य रखने वाला कोई भी पाठक उसे जाँच सकता है।

एक का अंतर, या ज़्यादा?

निजी सूचियों से एक अतिरिक्त रंग की ज़रूरत पड़ सकती है। क्या ज़्यादा की भी? तीन का अंतर एक बहुत अध्ययन किए गए संबंधी, सूची किनारा-रंगाई अनुमान (List Edge Colouring Conjecture), को भी गिरा देगा, क्योंकि χ″ℓ ≤ χ′ℓ + 2 और χ″ ≥ χ′। नोएल एक खुले सवाल के साथ समाप्त करते हैं, जिसे एआई का प्रति-उदाहरण अनछुआ छोड़ देता है: क्या हर ग्राफ़ के लिए χ″ℓ(G) ≤ χ″(G) + 1 है?