यादृच्छिक नेटवर्क एक तय घनत्व पर रंगने योग्य नहीं रह जाते
एक ग्राफ़ लीजिए — कड़ियों से जुड़े बिंदु — और रंगों का एक डिब्बा। q रंगों वाली एक उचित रंगाई (proper colouring) हर बिंदु को q में से एक रंग इस तरह देती है कि दो जुड़े हुए बिंदुओं का रंग कभी एक न हो। कम कड़ियों के साथ यह आसान है। बहुत सारी कड़ियों के साथ यह असंभव हो जाता है।
अब ग्राफ़ को यादृच्छिक रूप से बनाइए: n बिंदु, हर जोड़ा एक छोटी प्रायिकता के साथ स्वतंत्र रूप से जुड़ा, ताकि एक बिंदु के औसतन d पड़ोसी हों। जैसे-जैसे d बढ़ता है, यादृच्छिक ग्राफ़ “q रंगों से लगभग निश्चित रूप से (almost surely) रंगने योग्य” से “लगभग निश्चित रूप से नहीं” की ओर चला जाता है। यह बदलाव ठीक कहाँ होता है? तीन या उससे अधिक रंगों की किसी भी तय संख्या q के लिए, यही प्रश्न University of Cambridge में कार्यरत Gaia Carenini के एक नए शोधपत्र का विषय है।
एक बदलाव जो डगमगा सकता है
ग्रंथसूची में दर्ज 1999 के एक शोधपत्र में, Achlioptas और Friedgut ने सिद्ध किया कि यह संक्रमण तीक्ष्ण (sharp) है: हर आकार n के लिए एक क्रांतिक औसत डिग्री (critical average degree) d_q(n) होती है, जिससे थोड़ा नीचे ग्राफ़ लगभग निश्चित रूप से रंगने योग्य होता है, और थोड़ा ऊपर लगभग निश्चित रूप से नहीं। जिस खिड़की में बदलाव होता है, वह सिकुड़कर शून्य हो जाती है।
लेकिन इससे एक दरार रह गई। ऐसा कुछ नहीं था जो ग्राफ़ों के बड़े होने के साथ स्वयं क्रांतिक मान को दोलन करने से रोकता — एक आकार के ग्राफ़ों के लिए एक जगह, उनसे बड़े ग्राफ़ों के लिए थोड़ी दूसरी जगह, और कभी स्थिर न होना। Achlioptas–Friedgut अभिसरण अनुमान (convergence conjecture) कहता है कि ऐसा नहीं होता: हर q के लिए एक अकेला स्थिरांक d_q होता है, जिसके नीचे यादृच्छिक ग्राफ़ रंगने योग्य होते हैं और जिसके ऊपर नहीं।
भौतिकविदों ने क्या भविष्यवाणी की थी
सांख्यिकीय भौतिकी के पास इसकी एक तस्वीर थी कि क्या होता है। जैसे-जैसे कड़ियाँ जुड़ती हैं, वैध रंगाइयाँ गुच्छों (clusters) में बँट जाती हैं: एक गुच्छे के भीतर की रंगाइयाँ एक-दूसरे से मिलती-जुलती हैं, जबकि दो गुच्छे बहुत सारे बिंदुओं पर अलग होते हैं। फिर, संघनन (condensation) नामक एक चरण में, मुट्ठी भर बड़े गुच्छे सारी रंगाइयों का एक बड़ा हिस्सा समेट लेते हैं — और उसके बाद ही रंगाइयों का समुच्चय ख़ाली होता है। यही व्यवस्था बताती है कि दहलीज़ के पास गिनती पर आधारित तर्कों को इतनी कठिनाई क्यों होती है।
बहुत सारे रंगों के लिए, पहले के काम दहलीज़ को एक संकरे दायरे में बाँध चुके थे: वह लगभग 2q log q − log q − 2 log 2 और 2q log q − log q − 1 के बीच है, यानी q के बढ़ने पर 2 log 2 − 1 चौड़ाई का अंतराल। लेकिन “संकरा” होना “तय” होना नहीं है, और तीन जैसे कम रंगों के लिए प्रश्न खुला रहा।
एक जुड़वाँ समस्या, जिससे पहले निपटा गया
रंगाई की एक जुड़वाँ समस्या है: संतोषणीयता (satisfiability), यानी चरों के लिए सत्य या असत्य मान चुनने की समस्या, ताकि यादृच्छिक तार्किक शर्तों की एक सूची की सभी शर्तें पूरी हों। वहाँ भी एक तीक्ष्ण दहलीज़ का अस्तित्व ज्ञात था, बिना इस प्रमाण के कि वह स्थिर हो जाती है। शोधपत्र में उद्धृत 2026 की एक रिपोर्ट में, Carenini ने इस बात का प्रमाण घोषित किया कि वह स्थिर होती है, तीन या उससे अधिक हर शर्त-लंबाई (constraint length) के लिए, यह दिखाकर कि संक्रमण की खिड़की बहुत संकरी है। नया शोधपत्र उसी तर्क को रंगाई के लिए ढालता है।
जोड़े जो एक साथ जमे हुए हैं
प्रमाण अपचयनों (reductions) की एक शृंखला से होकर आगे बढ़ता है। एक-एक करके यादृच्छिक कड़ियाँ जोड़ते हुए, मान लीजिए H वह क्षण है जब ग्राफ़ रंगने योग्य नहीं रहता। यदि H एक यादृच्छिक ग्राफ़ से दूसरे तक थोड़ा ही बदलता है — लगभग n/(log n)² कड़ियों की खिड़की के भीतर — तो दहलीज़ को स्थिर होना ही होगा। एक शास्त्रीय असमिका इसे अंतिम रंगने योग्य ग्राफ़ के बारे में एक प्रश्न में बदल देती है: औसतन, वह कितनी नई यादृच्छिक कड़ियाँ झेल पाता है?
यहीं आती है मुख्य अवधारणा: जमे हुए जोड़े (frozen pairs)। दो बिंदु एक जमा हुआ जोड़ा बनाते हैं जब हर वैध रंगाई उन्हें एक ही रंग देती है। एक नई कड़ी ठीक तब घातक होती है जब वह ऐसे किसी जोड़े को जोड़ती है। अकेले बिंदु किसी एक ख़ास रंग में जमे नहीं हो सकते, क्योंकि रंगों की आपस में अदला-बदली से हमेशा एक और वैध रंगाई मिल जाती है; जो बाध्य होता है, वह दो बिंदुओं के बीच का एक संबंध है। Carenini ने इस पर नज़र रखी है कि कड़ियाँ जुड़ने के साथ ये जमे हुए वर्ग कैसे बढ़ते हैं: एक कड़ी या पूरा एक बिंदु हटाकर, और फिर से प्रकट होने वाले विकल्पों को देखकर। आकलन दिखाते हैं कि अंतिम रंगने योग्य ग्राफ़ ज़्यादा देर टिक नहीं सकता, जिससे खिड़की इतनी संकरी हो जाती है कि अनुमान सिद्ध हो जाए।
जो अभी अज्ञात है
प्रमेय कहता है कि दहलीज़ d_q हर q ≥ 3 के लिए मौजूद है। वह यह नहीं कहता कि दहलीज़ कहाँ है: शोधपत्र इसका कोई मान नहीं देता, तीन रंगों के लिए भी नहीं। शोधपत्र एकल-लेखक प्रीप्रिंट है और इसकी अभी सहकर्मी समीक्षा नहीं हुई है। यह एक छोटे कथन के साथ समाप्त होता है कि इसका कोई भी गणितीय तर्क किसी बड़े भाषा मॉडल (large language model) ने नहीं बनाया।
