1960 के दशक की एक ग्राफ़ पहेली आख़िरकार सुलझी

कुछ बिंदु लीजिए और उनमें से कुछ जोड़ियों को रेखाओं से जोड़ दीजिए: गणितज्ञ इसे ग्राफ़ कहते हैं, बिंदुओं को उसके शीर्ष (वर्टेक्स) और रेखाओं को उसके किनारे (एज)। चक्र (साइकल) एक बंद लूप है जो अलग-अलग शीर्षों से होकर अपनी शुरुआत पर लौट आता है। एक स्वाभाविक सवाल यह है कि क्या किसी ग्राफ़ के किनारों को — हर किनारे का ठीक एक बार इस्तेमाल करते हुए — चक्रों में बाँटा जा सकता है।

जैसा कि शोधपत्र याद दिलाता है, इसका जवाब लंबे समय से ज्ञात है: यह ठीक तब संभव है जब हर शीर्ष से सम संख्या में किनारे जुड़े हों। ऐसे ग्राफ़ों को ऑयलरी (Eulerian) ग्राफ़ कहते हैं। अगला सवाल यह है कि कितने चक्रों की ज़रूरत होगी। और जिन ग्राफ़ों में अकेले चक्रों से काम नहीं चलता, उनमें अकेले किनारों को भी टुकड़ों के रूप में स्वीकार किया जाता है।

अनुमान

1960 के दशक में एर्डोश (Erdős) और गलाई (Gallai) ने अनुमान लगाया कि n शीर्षों वाले हर ग्राफ़ के किनारों को ऐसे चक्रों और अकेले किनारों में बाँटा जा सकता है जिनकी संख्या अधिकतम n के अनुपात में हो — जिसे O(n) लिखा जाता है। एर्डोश ने इसे अनसुलझी समस्याओं के अपने कई संग्रहों में शामिल किया। हायोश (Hajós) का एक संबंधित अनुमान कहता है कि हर ऑयलरी ग्राफ़ के लिए अधिकतम (n − 1)/2 चक्र चाहिए।

रैखिक (लीनियर) ही वह सबसे अच्छी चीज़ है जिसकी उम्मीद की जा सकती है: एर्डोश ने दिखाया कि कुछ ग्राफ़ों को लगभग 1.5 n टुकड़े चाहिए। सवाल यह था कि क्या कोई स्थिरांक गुणा n हमेशा काफ़ी होता है।

पचास साल तक धीरे-धीरे खिसकती सीमाएँ

एर्डोश और गलाई ने ख़ुद एक सरल तरीक़ा देखा था: बार-बार सबसे लंबा चक्र हटाते जाइए। इससे लगभग n log n टुकड़े मिलते हैं — और शोधपत्र के अनुसार, यही लगभग पचास साल तक सबसे अच्छी सामान्य सीमा बनी रही। हाल में Conlon, Fox और Sudakov ने इसे घटाकर n log log n किया, फिर Bucić और Montgomery ने n log* n, जहाँ log* n — यानी एक से नीचे आने के लिए कितनी बार लघुगणक लेना पड़ता है — अकल्पनीय रूप से धीरे बढ़ता है। ये तरीक़े चरणों में काम करते थे, और हर चरण में लगभग n चक्र लगते थे, इसलिए चरणों की संख्या हमेशा अंतिम गिनती में घुस आती थी। यह अनुमान कुछ ख़ास परिवारों, जैसे यादृच्छिक (रैंडम) ग्राफ़ों, के लिए भी सिद्ध हो चुका था।

भार जो लूपों की क़ीमत चुकाते हैं

दक्षिण कोरिया के KAIST के Jaehoon Kim अब इस अनुमान को सिद्ध करते हैं: एक निश्चित स्थिरांक C है, जिसके लिए n शीर्षों वाला हर ग्राफ़ अधिकतम Cn चक्रों और किनारों में बँट जाता है। इसके परिणामस्वरूप, हायोश का अनुमान एक स्थिर गुणक तक सही ठहरता है।

यह प्रमाण चरणों को छोड़ देता है। एक अकेली प्रक्रिया एक-एक करके चक्र और किनारे हटाती है, और कुल संख्या दो राशियों से नियंत्रित होती है, जिनमें से हर एक किसी स्थिरांक गुणा n से नीचे रहती है।

• घातों (डिग्री) पर आधारित एक विभव। हर शीर्ष को एक भार मिलता है जो उसके किनारों की संख्या के साथ घटता है, लगभग 1 / (घात × log² घात)। कोई चक्र भारी है अगर उसके शीर्षों के भारों का योग कम से कम 1 हो। एक भारी चक्र हटाने से एक समग्र “विभव” (पोटेंशियल) कम से कम 1 घटता है, और यह विभव शुरुआत में किसी स्थिरांक गुणा n से ज़्यादा नहीं होता। इसलिए भारी चक्र सिर्फ़ O(n) बार ही हटाए जा सकते हैं।
• शीर्षों की संख्या। जब कोई भारी चक्र नहीं बचता, तो ग्राफ़ “हल्का” होता है — और मुख्य नया प्रमेय दिखाता है कि बड़ी घातों वाले हल्के ग्राफ़ में एक सघन, लगभग बंद क्षेत्र ज़रूर होता है। उस क्षेत्र को उसके आकार के अनुपात में चक्रों और किनारों में बाँटा जाता है, जिसके बाद उसके कम से कम पचासवें हिस्से के शीर्षों के पास अधिकतम दो किनारे बचते हैं और वे हमेशा के लिए बाहर हो जाते हैं। चूँकि हर शीर्ष सिर्फ़ एक बार बाहर हो सकता है, इस हिस्से की क़ीमत भी O(n) है।

ग्राफ़ के सघन हिस्सों के भीतर, पथों के टुकड़ों को “एक्सपैंडरों” से होकर गुज़रने वाले जोड़ने वाले पथों के ज़रिए एक अकेले चक्र में बंद किया जाता है; एक यादृच्छिक रंगाई एक ही चक्र के जोड़ने वाले पथों को अलग रखती है। — चित्र 3, Kim (2026), arXiv:2610.07840.

उन सघन क्षेत्रों को बाँटने के लिए, प्रमाण Bucić और Montgomery के मज़बूत “एक्सपैंडरों” (expanders) — ऐसे ग्राफ़ जिनमें शीर्षों के हर समूह के बहुत से पड़ोसी हों — के औज़ारों का विस्तार करता है, और शीर्षों को यादृच्छिक रूप से रंगता है ताकि एक ही चक्र के जोड़ने वाले पथ कभी आपस में न टकराएँ।

क्या अब भी खुला है

स्थिरांक C बहुत विशाल है, और लेखक ने उसे अनुकूलित करने की कोशिश नहीं की। सबसे अच्छा स्थिरांक — जो कम से कम 1.5 है — ढूँढना अब भी खुला सवाल है, वैसे ही हायोश का सटीक अनुमान और ग्राफ़ों को पथों में बाँटने पर गलाई का एक संबंधित अनुमान भी। भार वाली यह तरकीब बस ऐसे भार माँगती है जिनका योग अभिसारी (कन्वर्जेंट) हो, और लेखक का सुझाव है कि यह दूसरी विभाजन-समस्याओं में भी काम आ सकती है।

यह एक अकेले लेखक का प्रीप्रिंट है, जिसकी अभी सहकर्मी-समीक्षा से जाँच नहीं हुई है।

हितों का टकराव। लेखक बताते हैं कि उन्होंने तर्क विकसित करने और पाठ व चित्र तैयार करने में ChatGPT (OpenAI) और Claude (Anthropic) का बड़े पैमाने पर इस्तेमाल किया, और उन्होंने सभी परिणामों की पुष्टि की है तथा शोधपत्र की पूरी ज़िम्मेदारी लेते हैं। आप जो पाठ पढ़ रहे हैं, वह भी Claude ने ही लिखा है।