कोणत्याही नकाशासाठी चार रंग, रेषीय वेळेत शोधलेले

सपाट कागदावर काढलेला कोणताही नकाशा चार रंगांनी असा रंगवता येतो की शेजारी देशांचा रंग कधीच एकसारखा नसेल. Francis Guthrie यांनी 1852 मध्ये हे अनुमान मांडले; Appel आणि Haken यांनी 1976 मध्ये ते सिद्ध केले. पण हे प्रमेय फक्त एवढेच सांगते की चार रंग अस्तित्वात आहेत. दिलेल्या नकाशासाठी ते शोधायचे कसे? “याचे सोपे उत्तर नाही,” असे University of Tokyo चे Yuta Inoue आणि जपान, कॅनडा, स्लोव्हेनिया आणि डेन्मार्कमधील त्यांचे पाच सहकारी लिहितात. हा प्रश्न इतका गुंतागुंतीचा राहिला आहे की त्यातून अनेक प्रस्तावित प्रत्युदाहरणे पुढे आली.

ठिपके, रेषा आणि त्रिकोण

प्रत्येक देश एक ठिपका, म्हणजे शिरोबिंदू (vertex), बनतो आणि प्रत्येक सामायिक सीमा एक रेषा, म्हणजे कडा (edge): नकाशा एक समतलीय आलेख (planar graph) बनतो, जो रेषा एकमेकींना न छेदता काढलेला असतो. तो रंगवणे म्हणजे प्रत्येक शिरोबिंदूला चारपैकी एक रंग देणे, प्रत्येक कडेच्या दोन टोकांना वेगवेगळा. शिरोबिंदूंच्या संख्येला n म्हणू. त्रिकोणीकरणे (triangulations), जिथे प्रत्येक पृष्ठ त्रिकोण असते, हाताळणे पुरेसे आहे: अधिक कडा असल्या तर रंगवणे फक्त अधिक कठीण होते.

केम्पेची अदलाबदल

मूलभूत चाल A. B. Kempe यांच्या 1879 मधील एका शोधनिबंधापर्यंत मागे जाते. चार रंगांच्या जोड्या करा, उदाहरणार्थ लाल सोबत निळा आणि हिरवा सोबत पिवळा. केम्पे साखळी (Kempe chain) म्हणजे एका जोडीतील दोन रंग धारण करणाऱ्या शिरोबिंदूंचा जोडलेला गट. संपूर्ण साखळीवर ते दोन रंग अदलाबदल केल्यास रंगवण वैध राहते.

चार शेजारी असलेला एक शिरोबिंदू v घ्या, त्याच्याभोवती क्रमाने v0 ते v3, आणि उरलेला भाग आधी रंगवा. शेजारी तीन किंवा त्याहून कमी रंग वापरत असतील, तर v मोकळा रंग घेतो. ते चारही रंग वापरत असतील, तर v0 पासून सुरू होणारी, v0 आणि v2 च्या रंगांतील साखळी अनुसरा. ती v2 पर्यंत पोहोचत नसेल, तर तिची अदलाबदल करा: v0 ला v2 चा रंग मिळतो, आणि v साठी एक रंग मोकळा होतो. ती v2 पर्यंत पोहोचत असेल, तर त्याऐवजी v1 आणि v3 च्या रंगांतील v1 ची साखळी अदलाबदल करा, म्हणजे v1 ला v3 चा रंग मिळेल.

नेहमी दुरुस्त करता येणारे तुकडे

प्रमेयाच्या सिद्धता लघुकरणीय संरचनांवर (reducible configurations) आधारलेल्या आहेत: असे छोटे आकृतिबंध, जे कापून काढता येतात आणि उरलेला भाग रंगवल्यावर परत बसवता येतात. त्यांच्या वलयाचे (ring) — म्हणजे त्यांच्या अगदी भोवतीच्या शिरोबिंदूंचे — रंग जुळत नसतील, तर बाहेर केलेल्या, सुधारणा करणाऱ्या केम्पे-बदलांची एक मर्यादित संख्या ते नेहमी दुरुस्त करते: इथे वापरलेल्या आकृतिबंधांसाठी जास्तीत जास्त 25, ज्यांच्या वलयांत जास्तीत जास्त 18 शिरोबिंदू असतात.

एक लघुकरणीय संरचना (डावीकडे; प्रत्येक संख्या दर्शवते की संपूर्ण नकाशात त्या शिरोबिंदूला किती शेजारी असायलाच हवेत) आणि तिच्या वलय R ने पूर्ण केलेला तोच आकृतिबंध (उजवीकडे). — आकृती 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour आणि Thomas यांनी 1997 मध्ये दाखवले की अशा प्रकारे, एका वेळी एक आकृतिबंध घेऊन, रंगवण कसे करायचे. प्रत्येक टप्पा आलेख काही शिरोबिंदूंनी लहान करतो आणि त्यासाठी संपूर्ण आलेखावरून एक फेरी मारावी लागते, म्हणून वेळ वर्गात्मक (quadratic) असतो: दुप्पट मोठ्या नकाशासाठी चारपट अधिक वेळ.

याआधीच्या एका शोधनिबंधात (FOCS’26), याच सहा लेखकांनी सिद्ध केले की प्रत्येक त्रिकोणीकरणात, 8,202 आकृतिबंधांच्या एका यादीतून घेतलेल्या, एकमेकांना न स्पर्शणाऱ्या लघुकरणीय संरचना n च्या प्रमाणात असतात — किंवा दोन्ही बाजूंना शिरोबिंदू असलेली तितकीच छोटी चक्रे (loops), जी देखील उपयोगी पडतात. ते सर्व आकृतिबंध एकाच वेळी काढून टाकतात, उरलेला भाग रंगवतात, मग सर्व वलये एकत्र दुरुस्त करतात. एखादा यादृच्छिक केम्पे-बदल दिलेल्या वलयाला मदत करतो, जर त्याने रंगांची योग्य जोडणी निवडली (तीनमध्ये एक शक्यता) आणि वलयाला स्पर्श करणाऱ्या प्रत्येक साखळीवर नाणेफेकीचा योग्य कौल आला (प्रत्येकी दोनमध्ये एक शक्यता). अशा जास्तीत जास्त 18 साखळ्यांसह, ही शक्यता किमान 3 × 2¹⁸, म्हणजे 786,432 मध्ये एक आहे: लहान, पण स्थिर. म्हणून टप्प्यांची संख्या फक्त log n प्रमाणे वाढते, म्हणजे साधारण n ला जितक्या वेळा निम्मे करता येते तितकी. पण एकाच बदलात आलेखाचा एक स्थिर अंश गुंतलेला असू शकतो: प्रत्येक बदलासाठी एक पूर्ण फेरी लागते, एकूण n log n.

फेरीऐवजी एक तक्ता

नवा शोधनिबंध log n बदल तसेच ठेवतो, पण प्रत्येक बदल स्वस्त करतो. n च्या प्रमाणात वेळ घेणाऱ्या पूर्वतयारीनंतर, प्रत्येक बदल सरासरी सुमारे n / log n पायऱ्यांत शोधला आणि पार पाडला जातो. मग सर्व log n बदल मिळून n च्या प्रमाणात वेळ घेतात — रेषीय वेळ (linear time) — या मर्यादेला लेखक इष्टतम म्हणतात.

युक्ती आहे “Method of Four Russians” (चार रशियनांची पद्धत). ½ log n बिट्सच्या — म्हणजे n लिहिण्यासाठी लागणाऱ्या द्विमान अंकांच्या निम्म्या — एका संकेतात मावणाऱ्या उप-प्रश्नाच्या जास्तीत जास्त √n संभाव्य आवृत्त्या असतात, म्हणून त्या सर्वांची उत्तरे आधीच गणून एका तक्त्यात साठवता येतात. गृहीत धरलेला संगणक, ज्याचे स्मृती-शब्द सुमारे log n बिट्सचे असतात, कोणतेही साठवलेले उत्तर एका पायरीत वाचतो.

आलेख पुन्हा पुन्हा, लहान सीमा असलेल्या, एकमेकांत सामावलेल्या प्रदेशांत कापला जातो. सर्वात लहान प्रदेशांत सुमारे log n शिरोबिंदू असतात आणि ते, रंगांसह, एका संकेतात मावतात. प्रत्येक प्रदेशासाठी एक छोटा सारांश-आलेख नोंदवतो की कोणते सीमा-शिरोबिंदू एकच केम्पे साखळी सामायिक करतात. मग एखादा बदल “अदलाबदल करा” किंवा “तसेच ठेवा” अशा बिट्सच्या मालिकांच्या रूपात खाली उतरतो, आणि प्रत्येक लहान प्रदेशात एकाच तक्ता-शोधाने प्रत्येक रंग अद्ययावत होतो.

चार रंगांनी रंगवलेल्या आलेखाचा एक भाग. राखाडी भाग हा प्रदेश R आहे; जाड काळ्या कडा लाल-निळा आणि हिरवा-पिवळा या जोड्यांच्या केम्पे साखळ्यांच्या आहेत. — आकृती 2, Inoue et al. (2026), arXiv:2610.39753.

त्याच प्रदेशाचा सारांश: प्रत्येक निळा ठिपका केम्पे साखळीच्या एका तुकड्याचे प्रतिनिधित्व करतो, आणि त्याच्या रेषा दाखवतात की तो कोणते सीमा-शिरोबिंदू जोडतो. — आकृती 3, Inoue et al. (2026), arXiv:2610.39753.

फाशांशिवाय निवड

यादृच्छिक निवडींसह, हे आधीच एखादा नकाशा सरासरी रेषीय वेळेत रंगवते. वेग न गमावता फासे काढून टाकणे हा “कितीतरी अधिक आव्हानात्मक भाग” होता. आतापर्यंतचा प्रत्येक निर्णय एखाद्या वलयाच्या बाजूने गेला असेल, तर त्या वलयाला जिवंत म्हणू. त्याला स्पर्श करणाऱ्या u अनिर्णित साखळ्या नाणेफेकीवर सोडल्या असत्या, तर ते 1/2^u संभाव्यतेने टिकले असते; सर्व जिवंत वलयांवर बेरीज केल्यास, या संख्या टिकणाऱ्या वलयांची अपेक्षित संख्या देतात. एखाद्या साखळीचा निर्णय घेतल्याने ती निवड हवी असलेल्या प्रत्येक वलयाचे पद दुप्पट होते आणि इतरांचे शून्य होते. अल्गोरिदम असा पर्याय निवडतो ज्यामुळे बेरीज घसरत नाही, जेणेकरून शेवटी किमान तितक्या वलयांना मदत होते जितक्यांना योगायोगाने सरासरी झाली असती.

मर्यादा, स्टॉपवॉच नव्हे

शोधनिबंध कोणतीही अंमलबजावणी किंवा चालण्याचा वेळ नोंदवत नाही, आणि “n च्या प्रमाणात” मध्ये दडलेले स्थिरांक दिलेले नाहीत. ते मोठे आहेत: 8,202 आकृतिबंधांपैकी प्रत्येकासाठी, त्याच्या वलयाच्या प्रत्येक रंगवणीला किती सुधारणा करणारे बदल लागतात हे अल्गोरिदम साठवतो — “माहितीचे एक प्रचंड स्थिर प्रमाण”. एका परिशिष्टात, ते ज्यावर आधारित आहेत त्या एकमेकांत सामावलेल्या प्रदेशांच्या 2013 मधील एका रचनेतील “एक किरकोळ चूक” देखील दुरुस्त करतात. 1852 मधील एका अनुमानाला आता अशी रंगवण-पद्धती लाभली आहे, जिचा खर्च ती रंगवत असलेल्या नकाशापेक्षा अधिक वेगाने वाढत नाही.