यादृच्छिक जाळी एका ठरावीक घनतेवर रंगवता येईनाशी होतात
एक आलेख (graph) घ्या — दुव्यांनी जोडलेले ठिपके — आणि रंगांची एक पेटी. q रंगांसह केलेले योग्य रंगकाम (proper colouring) प्रत्येक ठिपक्याला q पैकी एक रंग अशा प्रकारे देते की जोडलेल्या दोन ठिपक्यांचा रंग कधीच सारखा नसतो. दुवे थोडे असतील तर हे सोपे आहे. ते पुष्कळ असतील तर ते अशक्य होते.
आता आलेख यादृच्छिकपणे बांधा: n ठिपके, प्रत्येक जोडी एका लहान संभाव्यतेने स्वतंत्रपणे जोडलेली, अशा प्रकारे की एका ठिपक्याला सरासरी d शेजारी असतात. d वाढत जातो तसा हा यादृच्छिक आलेख “q रंगांनी जवळजवळ निश्चितपणे रंगवता येणारा” यापासून “जवळजवळ निश्चितपणे न रंगवता येणारा” याकडे जातो. हा बदल नेमका कुठे होतो? तीन किंवा अधिक अशा कोणत्याही ठरावीक रंगसंख्येसाठी q, हा प्रश्न केंब्रिज विद्यापीठातील (University of Cambridge) गाया कारेनिनी (Gaia Carenini) यांच्या एका नव्या शोधनिबंधाचा विषय आहे.
डळमळू शकणारा एक बदल
ग्रंथसूचीत नोंदलेल्या 1999 मधील एका शोधनिबंधात, अख्लिओप्टास (Achlioptas) आणि फ्रीडगुट (Friedgut) यांनी सिद्ध केले की हे संक्रमण तीक्ष्ण (sharp) आहे: प्रत्येक आकार n साठी एक निर्णायक सरासरी शेजारी-संख्या (average degree) d_q(n) असते, अशी की तिच्या किंचित खाली आलेख जवळजवळ निश्चितपणे रंगवता येतो, आणि किंचित वर जवळजवळ निश्चितपणे नाही. ज्या खिडकीत हा बदल होतो ती आकुंचन पावत शून्यवत होते.
पण त्यामुळे एक पळवाट उरली. आलेख मोठे होत जातात तसे ते निर्णायक मूल्यच दोलायमान (oscillating) राहण्यापासून काहीही रोखत नव्हते — एका आकाराच्या आलेखांसाठी एका ठिकाणी, मोठ्या आलेखांसाठी किंचित वेगळीकडे, आणि कधीच स्थिर न होता. अख्लिओप्टास–फ्रीडगुट अभिसरण अटकळ (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 मधील एका अहवालात, कारेनिनी यांनी तीनपासून पुढील प्रत्येक अट-लांबीसाठी (constraint length) तो स्थिरावतो याची सिद्धता जाहीर केली होती, संक्रमणाची खिडकी अतिशय अरुंद असल्याचे दाखवून. नवा शोधनिबंध तो युक्तिवाद रंगकामासाठी जुळवून घेतो.
एकत्र गोठलेल्या जोड्या
सिद्धता घटीकरणांच्या (reductions) एका साखळीतून पुढे जाते. एकेक करून यादृच्छिक दुवे जोडताना, आलेख ज्या क्षणी रंगवता येईनासा होतो तो क्षण H मानू. जर H एका यादृच्छिक आलेखापासून दुसऱ्यापर्यंत फारसा बदलत नसेल — सुमारे n/(log n)² दुव्यांच्या खिडकीच्या आत — तर उंबरठा स्थिरावलाच पाहिजे. एक अभिजात असमता याचे रूपांतर शेवटच्या रंगवता येणाऱ्या आलेखाविषयीच्या प्रश्नात करते: सरासरी, तो किती नवे यादृच्छिक दुवे पचवून तग धरतो?
इथे येते मुख्य संकल्पना: गोठलेल्या जोड्या (frozen pairs). जेव्हा प्रत्येक वैध रंगकाम दोन ठिपक्यांना सारखाच रंग देते, तेव्हा ते दोन ठिपके एक गोठलेली जोडी बनवतात. एखादा नवा दुवा नेमका तेव्हाच घातक ठरतो जेव्हा तो अशी जोडी जोडतो. एकटे ठिपके एखाद्या विशिष्ट रंगावर गोठू शकत नाहीत, कारण रंगांची अदलाबदल केल्याने नेहमीच दुसरे वैध रंगकाम मिळते; जे सक्तीचे होते ते म्हणजे दोन ठिपक्यांमधील एक नाते. दुवे जोडले जातात तसे हे गोठलेले वर्ग कसे वाढतात याचा मागोवा कारेनिनी घेतात, एक दुवा किंवा संपूर्ण ठिपका काढून टाकून आणि पुन्हा प्रकट होणारे पर्याय पाहून. हे अंदाज दाखवतात की शेवटचा रंगवता येणारा आलेख फार काळ तग धरू शकत नाही, ज्यामुळे खिडकी अटकळ सिद्ध करण्याइतकी अरुंद होते.
अजूनही अज्ञात काय आहे
प्रमेय सांगते की उंबरठा d_q प्रत्येक q ≥ 3 साठी अस्तित्वात आहे. तो कुठे आहे हे ते सांगत नाही: शोधनिबंध त्याचे कोणतेही मूल्य देत नाही, अगदी तीन रंगांसाठीसुद्धा. हे पूर्वमुद्रण एकाच व्यक्तीने लिहिलेले आहे आणि त्याचे समवयस्क-परीक्षण झालेले नाही. ते एका छोट्या विधानाने संपते की त्यातील कोणताही गणितीय युक्तिवाद मोठ्या भाषा-प्रारूपाने (large language model) निर्माण केलेला नाही.
