1960 च्या दशकातील आलेखाचे कोडे अखेर सुटले

काही बिंदू घ्या आणि त्यांतील काही जोड्या रेषांनी जोडा: गणितज्ञ याला आलेख (graph) म्हणतात, बिंदूंना त्याचे शिरोबिंदू (vertices) आणि रेषांना त्याच्या कडा (edges). चक्र (cycle) म्हणजे भिन्न शिरोबिंदूंना भेट देऊन सुरुवातीच्या ठिकाणी परत येणारे बंद वर्तुळ. स्वाभाविक प्रश्न असा की आलेखाच्या कडा — प्रत्येक कडा बरोबर एकदाच वापरून — चक्रांमध्ये विभागता येतील का.

शोधनिबंध आठवण करून देतो त्याप्रमाणे, याचे उत्तर फार पूर्वीपासून माहीत आहे: प्रत्येक शिरोबिंदूला सम संख्येने कडा स्पर्श करत असतील, तेव्हा आणि तेव्हाच हे शक्य आहे. अशा आलेखांना ऑयलरीय (Eulerian) आलेख म्हणतात. पुढचा प्रश्न म्हणजे किती चक्रे लागतात. आणि ज्या आलेखांसाठी फक्त चक्रे पुरत नाहीत, त्यांच्यासाठी सुट्या कडाही तुकडे म्हणून चालतात.

अनुमान

1960 च्या दशकात एर्डॉश आणि गॅलाय (Erdős, Gallai) यांनी असे अनुमान मांडले की n शिरोबिंदू असलेल्या प्रत्येक आलेखाच्या कडा जास्तीत जास्त n शी प्रमाणात असलेल्या — O(n) असे लिहिले जाते — चक्रांमध्ये आणि सुट्या कडांमध्ये विभागता येतात. एर्डॉश यांनी हे आपल्या अनुत्तरित प्रश्नांच्या अनेक संग्रहांमध्ये समाविष्ट केले. हायोश (Hajós) यांचे एक संबंधित अनुमान विचारते की प्रत्येक ऑयलरीय आलेख जास्तीत जास्त (n − 1)/2 चक्रांमध्ये विभागता येतो का.

रेषीय (linear) हीच अपेक्षा करता येईल अशी सर्वोत्तम गोष्ट आहे: एर्डॉश यांनी दाखवले की काही आलेखांना सुमारे 1.5 n तुकडे लागतात. प्रश्न असा होता की n च्या एखाद्या स्थिर पटीने नेहमीच भागते का.

हळूहळू सरकणाऱ्या मर्यादांची पन्नास वर्षे

एर्डॉश आणि गॅलाय यांनी स्वतःच एक सोपी पद्धत लक्षात घेतली होती: पुन्हा पुन्हा सर्वात लांब चक्र काढून टाकणे. त्यातून सुमारे n log n तुकडे मिळतात — आणि शोधनिबंधानुसार, जवळपास पन्नास वर्षे हीच सर्वोत्तम सामान्य मर्यादा राहिली. अलीकडे, कॉनलन, फॉक्स आणि सुडाकोव्ह (Conlon, Fox, Sudakov) यांनी ती n log log n पर्यंत खाली आणली, नंतर बुचिच आणि मॉन्टगोमरी (Bucić, Montgomery) यांनी n log* n पर्यंत; इथे log* n — एकाखाली जाण्यासाठी किती वेळा लॉगरिदम घ्यावा लागतो ती संख्या — अकल्पनीय सावकाशपणे वाढते. हे दृष्टिकोन फेऱ्यांमध्ये काम करत, आणि प्रत्येक फेरीला सुमारे n चक्रे लागत, त्यामुळे फेऱ्यांची संख्या नेहमीच अंतिम मोजणीत शिरकाव करत असे. यादृच्छिक आलेखांसारख्या (random graphs) विशेष कुटुंबांसाठी हे अनुमान आधीच सिद्ध झाले होते.

वर्तुळांची किंमत चुकवणारी वजने

दक्षिण कोरियातील KAIST चे जेहून किम (Jaehoon Kim) आता हे अनुमान सिद्ध करतात: असा एक निश्चित स्थिरांक C आहे की n शिरोबिंदू असलेला प्रत्येक आलेख जास्तीत जास्त Cn चक्रे आणि कडांमध्ये विभागला जातो. उपसिद्धांत म्हणून, हायोश यांचे अनुमान एका स्थिर गुणकापर्यंत खरे ठरते.

ही सिद्धता फेऱ्यांचा मार्ग सोडून देते. एकच कार्यपद्धती चक्रे आणि कडा एकेक करून काढून टाकते, आणि एकूण संख्या दोन राशींनी नियंत्रित होते, ज्या प्रत्येकी n च्या स्थिर पटीच्या खाली राहतात.

• कोटींवर (degrees) आधारित स्थितिज. प्रत्येक शिरोबिंदूला त्याच्या कडांच्या संख्येनुसार कमी होत जाणारे वजन मिळते, साधारण 1 / (कोटी × log² कोटी). ज्या चक्रातील शिरोबिंदूंच्या वजनांची बेरीज किमान 1 असते, ते जड चक्र. जड चक्र काढून टाकल्याने एकूण “स्थितिज” (potential) किमान 1 ने कमी होते, आणि ही स्थितिज सुरुवातीला n च्या स्थिर पटीपेक्षा जास्त नसते. म्हणून जड चक्रे फक्त O(n) वेळाच काढता येतात.
• शिरोबिंदूंची संख्या. एकही जड चक्र उरले नाही, की आलेख “हलका” असतो — आणि मुख्य नवा प्रमेय दाखवतो की मोठ्या कोटी असलेल्या हलक्या आलेखात एक दाट, जवळजवळ बंदिस्त प्रदेश असलाच पाहिजे. तो प्रदेश त्याच्या आकाराशी प्रमाणात असलेल्या चक्रांमध्ये आणि कडांमध्ये विभागला जातो, आणि त्यानंतर त्याच्या शिरोबिंदूंपैकी किमान एक-पन्नासांश शिरोबिंदूंना जास्तीत जास्त दोन कडा उरतात आणि ते कायमचे बाहेर पडतात. प्रत्येक शिरोबिंदू एकदाच बाहेर पडू शकत असल्याने, या भागाची किंमतही O(n) असते.

आलेखाच्या दाट भागांमध्ये, “एक्स्पांडर”मधून जाणारे जोडमार्ग वापरून मार्गांचे तुकडे एकाच चक्रात बंद केले जातात; यादृच्छिक रंगवणीमुळे एकाच चक्राचे जोडमार्ग एकमेकांपासून दूर राहतात. — आकृती 3, Kim (2026), arXiv:2610.07840.

हे दाट प्रदेश विभागण्यासाठी, सिद्धता बुचिच आणि मॉन्टगोमरी यांच्या मजबूत “एक्स्पांडर” (expanders) — असे आलेख ज्यांत शिरोबिंदूंच्या प्रत्येक संचाला अनेक शेजारी असतात — या साधनसंचाचा विस्तार करते, आणि शिरोबिंदू यादृच्छिकपणे रंगवते, जेणेकरून एकाच चक्राचे जोडणारे मार्ग कधीही एकमेकांवर आदळत नाहीत.

अजून काय अनुत्तरित आहे

स्थिरांक C प्रचंड मोठा आहे, आणि लेखकाने तो इष्टतम करण्याचा प्रयत्न केलेला नाही. सर्वोत्तम स्थिरांक — किमान 1.5 — शोधणे अजून अनुत्तरित आहे, तसेच हायोश यांचे नेमके अनुमान आणि आलेख मार्गांमध्ये विभागण्याबाबतचे गॅलाय यांचे संबंधित अनुमानही. वजनांच्या युक्तीला फक्त ज्यांची बेरीज अभिसारी (convergent) असते अशी वजने लागतात, आणि लेखक सुचवतात की ती इतर विभाजन प्रश्नांमध्येही उपयोगी ठरू शकेल.

हे एकाच लेखकाचे प्रीप्रिंट आहे, अजून समीक्षकांनी (peer review) तपासलेले नाही.

हितसंबंधांचा संघर्ष. लेखक नमूद करतात की युक्तिवाद विकसित करताना आणि मजकूर व आकृत्या तयार करताना त्यांनी ChatGPT (OpenAI) आणि Claude (Anthropic) यांचा मोठ्या प्रमाणावर वापर केला, आणि सर्व निकाल त्यांनी स्वतः पडताळले असून शोधनिबंधाची संपूर्ण जबाबदारी त्यांची आहे. तुम्ही वाचत असलेला हा मजकूरही Claude ने लिहिला आहे.