जाळ्यांवरील एक मर्यादा, आता प्रत्येक आकारासाठी सिद्ध

काही बिंदू घ्या आणि त्यांच्यातील काही जोड्या रेषांनी जोडा. गणितज्ञ याला आलेख (graph) म्हणतात: बिंदू हे त्याचे शिरोबिंदू, रेषा या त्याच्या कडा, आणि दोन शिरोबिंदूंमधील अंतर म्हणजे एकाकडून दुसऱ्याकडे चालत जाण्यासाठी लागणाऱ्या कमीत कमी कडा. आता दोन नियम जोडा. शिरोबिंदूंची प्रत्येक जोडी जास्तीत जास्त 2 अंतरावर असली पाहिजे — थेट जोडलेली, किंवा एखाद्या सामायिक शेजाऱ्यामार्फत. आणि एकही कडा अतिरिक्त असता कामा नये: कोणतीही एक कडा काढून टाका, आणि एखादी जोडी दोनपेक्षा जास्त पावलांच्या अंतरावर जाते. अशा आलेखाला व्यास-2-क्रांतिक (diameter-2-critical) म्हणतात. त्यात जास्तीत जास्त किती कडा असू शकतात?

Mantel यांचे छत, आणि एक धाडसी अंदाज

1907 मध्ये Mantel यांनी सिद्ध केले की n शिरोबिंदूंच्या, त्रिकोण नसलेल्या आलेखात — म्हणजे जिथे कोणतेही तीन शिरोबिंदू एकमेकांशी परस्पर जोडलेले नाहीत — जास्तीत जास्त ⌊n²/4⌋ कडा असतात: n चा वर्ग भागिले चार, खालच्या पूर्ण संख्येपर्यंत पूर्णांकित. फक्त एकच आलेख हे छत गाठतो, तो म्हणजे संतुलित पूर्ण द्विभाजित आलेख (balanced complete bipartite graph): आकाराने शक्य तितके समान दोन गट, एका गटातील प्रत्येक शिरोबिंदू दुसऱ्या गटातील प्रत्येक शिरोबिंदूशी जोडलेला, आणि गटाच्या आत एकही कडा नाही.

ज्या त्रिकोणरहित आलेखात त्रिकोण निर्माण न करता आणखी एकही कडा जोडता येत नाही, तो प्रत्येक आलेख व्यास-2-क्रांतिक असतो. उलट मात्र खरे नाही: काही व्यास-2-क्रांतिक आलेखांमध्ये त्रिकोण असतात.

7 शिरोबिंदू आणि 9 कडा असलेला एक व्यास-2-क्रांतिक आलेख, ज्यात v1v3v5 हा त्रिकोण आहे. v1v3 काढून टाकल्यास v2 आणि v3 मधील दोन पावलांचा एकमेव मार्ग नष्ट होतो; त्रिकोणाबाहेरील एखादी कडा काढून टाकल्यास तिच्या दोन टोकांमध्ये दोन पावलांचा कोणताही मार्ग उरत नाही. — आकृती 1, Das & Fox (2026), arXiv:2610.39032.

अंदाज असा होता की त्रिकोणांमुळे काहीच फायदा होत नाही: n शिरोबिंदूंच्या व्यास-2-क्रांतिक आलेखात तरीही जास्तीत जास्त ⌊n²/4⌋ कडाच असतात, आणि संतुलित पूर्ण द्विभाजित आलेख हाच ते छत गाठणारा एकमेव आलेख राहतो. Mantel यांचे प्रमेय मग त्याचीच एक विशेष स्थिती म्हणून मिळाले असते. आकृतीतील 7 शिरोबिंदूंसाठी हे छत 12 कडांचे आहे.

2 चा एक मनोरा

Zoltán Füredi यांनी नोंदवल्यानुसार, Erdős यांच्या मते हा प्रश्न 1960 च्या दशकातील Ore यांच्या कामापर्यंत मागे जातो. Ján Plesník यांनी 1975 मध्ये कडांची ही मर्यादा एक अटकळ म्हणून मांडली; Murty आणि Simon यांनी ती स्वतंत्रपणे सुचवली आणि त्यात भर घातली की संतुलित पूर्ण द्विभाजित आलेख ही एकमेव टोकाची स्थिती आहे — म्हणून तिचे नाव Murty–Simon अटकळ. 1970 आणि 1980 च्या दशकांत c·n² या स्वरूपाच्या मर्यादा हळूहळू खाली सरकत गेल्या, आणि c सतत 1/4 च्या अधिक जवळ येत गेला.

1992 मध्ये Füredi यांनी नियमितता पद्धती (regularity methods) वापरून — Szemerédi यांच्या नियमितता प्रमेयिकेतून (regularity lemma) निघालेली साधने — पुरेशा मोठ्या प्रत्येक n साठी ही अटकळ सिद्ध केली. त्याची किंमत होती सुरुवातीचा आकार: n किमान सुमारे 10¹⁴ उंचीच्या 2 च्या मनोऱ्याइतका असावा लागत होता, म्हणजे 2 चा घात 2 चा घात 2…, जो वरून खाली सोडवला जातो — प्रत्येक 2 त्याच्या वरच्या सगळ्याच्या घातावर नेला जातो — त्या रचनेत सुमारे 10¹⁴ दोन एकावर एक. त्या आकाराखाली फक्त आलेखांच्या काही विशेष कुटुंबांचाच प्रश्न सुटला होता.

कडा विरुद्ध नसलेल्या कडा

Stanford University च्या गणित विभागातील Sanjana Das आणि Jacob Fox यांची ही नवी सिद्धता 3 पासून पुढील प्रत्येक n साठी लागू होते. ती एक कमाल जुळणी (maximal matching) वापरते: कडांचा असा संच, ज्यातील कोणत्याही दोन कडांमध्ये सामायिक शिरोबिंदू नाही, आणि ज्यात आणखी एखादी कडा जोडल्यास त्यातील दोन कडा एकमेकींना भेटतातच. n शिरोबिंदूंवरील जुळणीत जास्तीत जास्त ⌊n/2⌋ कडा असतात.

मुख्य प्रमेयिका अशी: व्यास-2-क्रांतिक आलेखात, कोणत्याही कमाल जुळणीसाठी, जुळणीबाहेरील कडा अ-कडांपेक्षा (non-edges) — म्हणजे जोडलेल्या नसलेल्या शिरोबिंदूंच्या जोड्यांपेक्षा — कधीच जास्त नसतात. बाकी सगळे अंकगणित आहे. कडांच्या संख्येची दुप्पट ही जोड्यांची संख्या अधिक जुळणीचा आकार यांच्यापेक्षा जास्त नसते. 10 शिरोबिंदूंसाठी: 45 जोड्या अधिक जास्तीत जास्त 5 जुळणी-कडा मिळून 50, म्हणून जास्तीत जास्त 25 कडा. प्रत्येक n साठी ही बेरीज Mantel यांच्या छताच्या बरोबर दुप्पट येते.

ही प्रमेयिका स्वतः काटेकोर हिशेबनिसीचे काम आहे. एखादी अ-कडा क्रांतिक (critical) असते, जर तिच्या टोकांना दोन पावलांचा एकच मार्ग जोडत असेल — आकृती 1 मधील सर्व बारा अ-कडांबाबत असेच आहे. लेखक प्रत्येक क्रांतिक अ-कडेला तिच्या मार्गावरील दोन कडांशी जोडतात आणि त्यातून तयार होणाऱ्या जाळ्याचे जोडलेले तुकडे करतात. एका तुकड्यात क्रांतिक अ-कडांपेक्षा जास्तीत जास्त एक कडा अधिक असते, आणि असे अधिशेष असलेल्या प्रत्येक तुकड्याची भरपाई एखाद्या अ-क्रांतिक अ-कडेने करावी लागते. त्या शोधण्यासाठी लेखक अदलाबदल निर्गम (switch exits) वापरतात: तुकड्यातील एखादी कडा किंवा क्रांतिक अ-कडा घ्या आणि तिचे एक टोक जुळणीतील त्या टोकाच्या जोडीदाराशी अदलाबदल करा. प्रत्येक अ-क्रांतिक अ-कडेवर जास्तीत जास्त दोनदा दावा केला जातो, अधिशेष असलेला प्रत्येक तुकडा किमान दोन दावे करतो, आणि हिशेब पूर्ण होतो.

कोणी काय शोधले

“ही सिद्धता बहुतांशी AI ने शोधली, विशेषतः 11 ऑगस्ट 2026 रोजी GPT-5.6 Sol ने,” असे लेखक AI विषयीच्या एका छोट्या निवेदनात लिहितात. मॉडेलने ⌊n²/4⌋ मर्यादेची एक पूर्ण सिद्धता शोधली, जी त्यांनी सोपी केली. सम संख्येच्या शिरोबिंदूंसाठी, त्याने हेही सिद्ध केले की संतुलित पूर्ण द्विभाजित आलेख ही एकमेव टोकाची स्थिती आहे; त्यासाठी त्याने Sumner यांनी सिद्ध केलेल्या एका तथ्याचा आधार घेतला, जे अशा आलेखांविषयी आहे ज्यांतील प्रत्येक कमाल जुळणी परिपूर्ण (perfect) असते, म्हणजे प्रत्येक शिरोबिंदूला सामावून घेते.

विषम संख्येच्या शिरोबिंदूंसाठी कोणतीही जुळणी परिपूर्ण नसते, आणि अनेक आलेखांत प्रत्येक कमाल जुळणीतून बरोबर एक शिरोबिंदू सुटतो: मॉडेलचा युक्तिवाद या स्थितीसाठी जुळवून घेता आला नाही. लेखकांनी समानतेच्या स्थितीची, प्रत्येक n साठी लागू होणारी, एक वेगळी सिद्धता शोधली आणि शोधनिबंध स्वतः लिहिला; GPT-6 Astra मधून केलेल्या शेवटच्या फेरीतून “काही किरकोळ दुरुस्त्या” झाल्या. हा शोधनिबंध एक प्रीप्रिंट आहे, अजून समकक्ष-समीक्षित (peer-reviewed) नाही, आणि त्यात या युक्तिवादाच्या संगणकाने पडताळलेल्या आवृत्तीचा उल्लेख नाही.

पुन्हा 1907 कडे

एखादा आलेख छताची बरोबरी करत असेल, तर मुख्य असमता प्रत्येक कमाल जुळणीसाठी समता बनते. जुळण्या चतुराईने निवडून लेखक दाखवतात की असा आलेख एकतर तारा (star) असतो — एक शिरोबिंदू इतर सर्वांशी जोडलेला, बाकी काहीच नाही — किंवा त्यात एकही क्रांतिक अ-कडा नसते. व्यास-2-क्रांतिक आलेखात त्रिकोणाची प्रत्येक कडा कोणत्या ना कोणत्या क्रांतिक मार्गावर असते, म्हणून क्रांतिक अ-कडा नाही म्हणजे त्रिकोण नाही; ताऱ्यातही त्रिकोण नसतो. म्हणून बरोबरी करणारा आलेख त्रिकोणरहित असतो, आणि शेवटची पायरी म्हणजे तेच प्रमेय, जे अधिक बळकट करण्यासाठी ही अटकळ निघाली होती: Mantel यांचा 1907 चा निकाल, जो संतुलित पूर्ण द्विभाजित आलेखालाच छतावर एकटा ठेवतो.