🔢 mathematics

On Alternating 6-Cycles in Edge-Coloured Graphs

फ्लैग अलजेब्रा का उपयोग करते हुए, यह शोध पत्र सिद्ध करता है कि एक समान रूप से यादृच्छिक लाल/नीले किनारे का रंग (red/blue edge coloring) एक बड़े क्लीक (clique) में रंग-परिवर्तित होने वाले 6-चक्रों (color-alternating 6-cycles) की संख्या को स्पर्शिक रूप से (asymptotically) अधिकतम करता है, जिससे बासित एट अल द्वारा प्रस्तुत एक समस्या के पहले खुले मामले का समाधान होता है।

मूल लेखक: Hao Chen, Jonathan A. Noel

प्रकाशित 2026-07-17

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Hao Chen, Jonathan A. Noel

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल पार्टी में हैं जहाँ हर कोई या तो लाल शर्ट या नीली शर्ट पहने हुए है। अब, कल्पना कीजिए कि इस पार्टी के हर जोड़े ने आपस में हाथ मिलाया है, और हर हाथ मिलाना (handshake) या तो एक "लाल हाथ मिलाना" है या एक "नीला हाथ मिलाना"। यह रंगों से भरा जुड़ाव का जो उलझा हुआ जाल आपने देखा, इसे गणितज्ञ "एज-कलर्ड ग्राफ" (edge-colored graph) कहते हैं। सवाल जो कुछ बहुत जिज्ञासु लोगों को रात भर जगाए रखता है वह यह है कि यदि आप इस जाल में किसी विशिष्ट पैटर्न की तलाश करें—मान लीजिए छह लोगों का एक घेरा जहाँ हाथ मिलाने के रंग बारी-बारी से बदलते हैं जैसे लाल-नीला-लाल-नीला-लाल-नीला—तो आप ऐसे कितने पैटर्न खोज सकते हैं?

यह सिर्फ एक पार्टी का खेल नहीं है; यह गणित की एक शाखा है जिसे "एक्सट्रीमल कॉम्बिनेटरिक्स" (extremal combinatorics) कहा जाता है। यह बड़े सिस्टम में पैटर्न की परम सीमाओं को खोजने का अध्ययन है। इसे ऐसे समझें जैसे कि पूछना कि, "दीवार बनाने के लिए ईंटों को व्यवस्थित करने का सबसे कुशल तरीका क्या है?" या "एक कागज को कितनी बार मोड़ने का अधिकतम संभव है?" इस मामले में, "ईंटें" हाथ मिलाना हैं, और "दीवार" ग्राफ की संरचना है। गणितज्ञों को इसकी परवाह इसलिए है क्योंकि इन सीमाओं को समझना हमें कंप्यूटर नेटवर्क से लेकर सामाजिक संरचनाओं तक, हर चीज़ में व्यवस्था (order) और अराजकता (chaos) के बीच के अंतर्संबंधों को समझने में मदद करता है। कभी-कभी, सबसे "रैंडम" दिखने वाली व्यवस्था ही वह होती है जो एक विशिष्ट पैटर्न को सबसे अधिक बनाती है, और कभी-कभी, एक बहुत ही विशिष्ट, संगठित संरचना विजेता होती है। इसे समझना एक ब्रह्मांडीय पहेली को सुलझाने जैसा है।

इस संक्षिप्त लेकिन तीखी टिप्पणी में, दो गणितज्ञ, हाओ चेन और जोनाथन ए. नोएल, इस पहेली के एक विशिष्ट हिस्से को सुलझाते हैं। वे जानना चाहते थे कि एक विशाल, पूरी तरह से जुड़े हुए पार्टी में, जहाँ हर हाथ मिलाना रैंडम तरीके से लाल या नीला चुना गया है, क्या वह रैंडम अराजकता उन वैकल्पिक छह-व्यक्ति चक्रों (जिन्हें अल्टरनेटिंग 6-साइकिल कहा जाता है) की संख्या को अधिकतम करने का सबसे अच्छा तरीका है?

लंबे समय तक, यह एक खुला प्रश्न था। हालांकि वे अन्य आकृतियों (जैसे वैकल्पिक पथ या चार की संख्या से विभाज्य लंबाई वाले चक्र) के लिए उत्तर जानते थे, लेकिन 6-साइकिल का मामला एक जिद्दी रहस्य बना रहा। लेखकों ने इस कोड को तोड़ने के लिए "फ्लैग अल्जेब्रा" (flag algebras) नामक एक शक्तिशाली गणितीय उपकरण का उपयोग किया। आप फ्लैग अल्जेब्रा को एक सुपर-चार्ज्ड माइक्रोस्कोप की तरह समझ सकते हैं जो गणितज्ञों को एक ग्राफ के छोटे टुकड़ों पर ज़ूम करने, उनके अंदर के पैटर्न गिनने और फिर उन छोटे काउंट्स का उपयोग यह निष्कर्ष निकालने के लिए करने की अनुमति देता है कि पूरा विशाल ग्राफ कैसा होना चाहिए। यह बिल्कुल वैसा ही है जैसे किसी विशाल सूप के स्वाद का अनुमान लगाने के लिए केवल कुछ चम्मच सामग्री चखना और सामग्रियों के अनुपात पर भारी गणित का उपयोग करना।

पेपर एक निश्चित परिणाम सिद्ध करता है: इन वैकल्पिक 6-साइकल्स की अधिकतम संख्या वास्तव में तब प्राप्त होती है जब रंगों को पूरी तरह से रैंडम तरीके से चुना जाता है।

यहाँ मुख्य बात है: यदि आपके पास एक विशाल क्लीक (एक ऐसा समूह जहाँ हर कोई हर किसी से जुड़ा हुआ है) है और आप कनेक्शन को रैंडम तरीके से रंगते हैं—हर हाथ मिलाना लाल या नीला तय करने के लिए एक सिक्का उछालकर—तो आप किसी भी अन्य चतुर, पूर्व-नियोजित कलरिंग स्कीम की तुलना में अधिक वैकल्पिक 6-साइकिल प्राप्त करेंगे। पेपर दिखाता है कि ऐसे रैंडम ग्राफ में इन चक्रों का घनत्व (density) ठीक $(1/2)^6$ , यानी $1/64$ है।

लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने एक कठोर प्रमाण प्रदान किया। उन्होंने एक छोटे समूह के छह लोगों (विशेष रूप से, एक बाइपार्टाइट ग्राफ जिसे $K_{3,3}$ कहा जाता है) के सभी संभावित तरीकों का विश्लेषण करके समस्या को सुलझाया। इस छोटे समूह के किनारों (edges) को लाल और नीले रंग से रंगने के 512 तरीके हैं। इन 512 संभावनाओं को 26 अद्वितीय "आकृतियों" (रोटेशन और फ्लिप को छोड़कर) में समूहित करके, वे एक विशाल समीकरण प्रणाली स्थापित करने में सक्षम रहे।

उन्होंने "फ्लैग्स" (flags) का उपयोग करते हुए एक चतुर तकनीक पेश की—छोटे ग्राफ जिनमें दो विशेष "रूट" वर्टिस (vertices) होते हैं। इन फ्लैग्स के जुड़ने के तरीके का विश्लेषण करके, उन्होंने संख्याओं का एक विशाल 8-बाय-8 मैट्रिक्स बनाया। यह मैट्रिक्स एक गणितीय सुरक्षा जाल की तरह कार्य करता है; यह "पॉजिटिव सेमी-डेफिनिट" (positive semi-definite) है, जिसका अर्थ है कि आप अपने विशाल ग्राफ में रंगों को कैसे भी व्यवस्थित करें, गणित मजबूर करता है कि वैकल्पिक 6-साइकल्स की संख्या एक निश्चित सीमा से नीचे रहे। जब उन्होंने गणना की, तो वह सीमा ठीक $(1/2)^6$ निकली।

इस प्रकार, यह पेपर बासित और उनके सहयोगियों द्वारा प्रस्तुत एक बड़ी समस्या के पहले खुले मामले को सुलझाता है। यह पुष्टि करता है कि इस विशिष्ट आकृति के लिए, प्रकृति व्यवस्था (order) के बजाय रैंडमनेस (randomness) को प्राथमिकता देती है। लेखक यह भी नोट करते हैं कि जबकि उनकी विधि इस विशिष्ट मामले के लिए शानदार है, लेकिन यह बहुत बड़े या अधिक जटिल आकृतियों के लिए बहुत भारी हो सकती है, क्योंकि पैटर्न कॉम्बिनेटोरियली विस्फोट कर जाते हैं। हालाँकि, उनका काम दृढ़ता से सुझाव देता है कि अन्य समान आकृतियों (जैसे 10, 14 आदि लंबाई वाले चक्र) के लिए भी, रैंडम कलरिंग ही चैंपियन हो सकती है।

दिलचस्प बात यह है कि पेपर में उल्लेख है कि शोधकर्ताओं के एक अन्य समूह ने समान तरीकों का उपयोग करके स्वतंत्र रूप से एक ही निष्कर्ष पर पहुँचा है। लेकिन चेन और नोएल के लिए, यात्रा यह दिखाने के बारे में थी कि लाल और नीले रंग की अराजकता के समुद्र में भी, सबसे "रैंडम" व्यवस्था ही इन विशिष्ट वैकल्पिक लूपों को बनाने के लिए सबसे अधिक उत्पादक है। यह एक याद दिलाता है कि कभी-कभी, एक पैटर्न बनाने का सबसे अच्छा तरीका बस पासे फेंक देना होता है।

समस्या विवरण
यह शोध पत्र किनारों से रंगित (edge-coloured) ग्राफों के लिए "अर्ध-प्रेरणीयता समस्या" (semi-inducibility problem) को संबोधित करता है, जो विशेष रूप से एक बड़े लाल/नीले किनारों वाले क्लीक (clique) में वैकल्पिक 6-चक्रों ( $CA_6$ ) के अधिकतम घनत्व पर केंद्रित है। एक वैकल्पिक चक्र $CA_{2k}$ को एक ऐसे चक्र के रूप में परिभाषित किया गया है जहाँ प्रत्येक शीर्ष (vertex) ठीक एक किनारे से प्रत्येक रंग का जुड़ा होता है। केंद्रीय प्रश्न, जिसे बासित एट अल. [1] द्वारा प्रस्तुत किया गया था, एक किनारों से रंगित ग्राफ $G$ में ऐसी संरचनाओं की होमोमोर्फिक प्रतियों की अधिकतम संख्या निर्धारित करना है। जबकि पिछले कार्यों ने सम और विषम लंबाई के वैकल्पिक पथों, साथ ही चार से विभाज्य लंबाई के वैकल्पिक चक्रों के मामलों को हल कर दिया था, $2 \pmod 4$ की लंबाई वाले वैकल्पिक चक्रों (जैसे कि $CA_6$ ) के लिए मामला खुला रह गया था।

कार्यप्रणाली
लेखक एक एसिम्प्टोटिक ऊपरी सीमा (asymptotic upper bound) प्राप्त करने के लिए फ्लैग अलजेब्रा विधि (flag algebra method) का उपयोग करते हैं, जो राजज़ोबव [3] द्वारा प्रस्तुत एक सेमी-डेफिनेट प्रोग्रामिंग तकनीक है। प्रमाण निम्नलिखित तकनीकी चरणों के माध्यम से आगे बढ़ता है:

इंजेक्टिव होमोमॉर्फिज्म में न्यूनीकरण: समस्या को पहले सामान्य होमोमॉर्फिज्म से इंजेक्टिव होमोमॉर्फिज्म ( $t_{inj}$ ) में घटाया जाता है, यह दिखाते हुए कि इंजेक्टिव मानचित्रों के लिए सीमा सिद्ध करना "ब्लो-अप" तर्क के माध्यम से सामान्य मानचित्रों के लिए परिणाम सिद्ध करने का संकेत देता है।
$K_{3,3}$ के माध्यम से अपघटन: लेखक देखते हैं कि एक बड़े क्लीक से 6-चक्र के किसी भी इंजेक्टिव मानचित्र का विश्लेषण एक पूर्ण द्विपक्षीय उपग्राफ (complete bipartite subgraph) $K_{3,3}$ के भीतर चक्र के प्रतिबिंब को मानकर किया जा सकता है। $K_{3,3}$ के $2^9 = 512$ विशिष्ट लाल/नीले रंग के संयोजन हैं।
आइसोमोर्फिज्म क्लासेस और फ्लैग्स: इन 512 संयोजनों को 26 गैर-आइसोमोर्फिक वर्गों ( $J_1, \dots, J_{26}$ ) में समूहीकृत किया गया है। $CA_6$ के घनत्व को इन 26 वर्गों के घनत्वों के एक रैखिक संयोजन के रूप में व्यक्त किया जाता है, जो इस भार द्वारा भारित होता है कि $K_{3,3}$ से $C_6$ का एक यादृच्छिक होमोमॉर्फिज्म किसी विशिष्ट वर्ग में मैप होता है।
फ्लैग अलजेब्रा असमानताएँ: इस रैखिक संयोजन को बांधने के लिए, लेखक दो रूटेड वर्टिस (rooted vertices) वाले 16 "फ्लैग्स" पेश करते हैं, जिन्हें $R_1, \dots, R_8$ और $B_1, \dots, B_8$ के रूप में नामित किया गया है। वे एक $8 \times 8$ पॉजिटिव सेमी-डेफिनेट मैट्रिक्स $A$ का निर्माण करते हैं। $\vec{x}_{u,v}^T A \vec{x}_{u,v}$ और $\vec{y}_{u,v}^T A \vec{y}_{u,v}$ (जहाँ $\vec{x}$ और $\vec{y}$ फ्लैग्स से $G$ के होमोमॉर्फिज्म के काउंट का प्रतिनिधित्व करते हैं) क्वाड्रेटिक फॉर्म्स पर विचार करके, वे एक असमानता व्युत्पन्न करते है जो $CA_6$ के घनत्व को 26 आइसोमोर्फिज्म वर्गों के घनत्वों से जोड़ती है।
संख्यात्मक सत्यापन: प्रमाण परिशिष्ट A में दिए गए विस्तृत संख्यात्मक गणना के साथ समाप्त होता है, जो दिखाता है कि व्युत्पन्न असमानता में $d(J_\ell, G)$ के घनत्वों के गुणांक ठीक $(1/2)^6$ के बराबर होते हैं।

मुख्य परिणाम
यह शोध पत्र निम्नलिखित प्रमेय स्थापित करता है:
प्रमेय 1.1: प्रत्येक किनारों से रंगित ग्राफ $G$ संतुष्ट करता है $t(CA_6, G) \le (1/2)^6$ ।

लेखक प्रदर्शित करते हैं कि यह सीमा एसिम्प्टोटिक रूप से टाइट (tight) है, क्योंकि इसे एक समान रूप से यादृच्छिक (uniformly random) किनारों वाले क्लीक द्वारा प्राप्त किया जाता है। इसके अलावा, प्रमाण यह निहित करता है कि किनारों से रंगित क्लीक का एक अनुक्रम इस अधिकतम घनत्व को तब प्राप्त करता है जब और केवल तभी जब वह क्वासिरैंडम (quasirandom) हो (अर्थात, लाल किनारे एक क्वासिरैंडम ग्राफ बनाते हैं)।

महत्ता और दावे
यह शोध पत्र दावा करता है कि यह $2 \pmod 4$ की लंबाई वाले वैकल्पिक चक्रों (विशेष रूप से $CA_6$ ) के लिए अर्ध-प्रेरणीयता समस्या के पहले खुले मामले को हल करता है, जैसा कि बासित एट अल. [1] के समस्या 9.1 में प्रस्तावित किया गया था। लेखक नोट करते हैं कि यह परिणाम स्वतंत्र रूप से बालोग, लिडिकी, मुबायी और फेंडर द्वारा समान फ्लैग अलजेब्रा तकनीकों का उपयोग करके प्राप्त किया गया था।

उनकी विधि की व्यापक प्रयोज्यता के संबंध में, लेखक विनम्र हैं। वे कहते हैं कि अधिक वर्टिस वाले ग्राफों को संभालने में शामिल कॉम्बिनेटोरियल विस्फोट के कारण फ्लैग अलजेब्रा विधि के लिए सभी वैकल्पिक चक्रों ( $2 \pmod 4$ लंबाई वाले) के लिए सामान्य प्रमाण की संभावना कम है। हालांकि, वे सुझाव देते हैं कि यहाँ उपयोग किया गया विशिष्ट दृष्टिकोण— $K_6$ के 156 संयोजनों के बजाय $K_{3,3}$ के 26 गैर-आइसोमोर्फिक संयोजनों पर निर्भर करना, और छूटे हुए किनारों वाले फ्लैग्स का उपयोग करना—यह दर्शाता है कि "सरल" फ्लैग अलजेब्रा प्रमाण कभी-कभी विधि की पहुंच बढ़ा सकते हैं या उन प्रमेयों के लिए मानव-जांच योग्य प्रमाण प्रदान कर सकते हैं जिनके लिए आमतौर पर कंप्यूटर सत्यापन की आवश्यकता होती है। यह शोध पत्र इन अवलोकनों के परे कोई नए प्रायोगिक अनुप्रयोग या भविष्य के अनुसंधान दिशाओं का प्रस्ताव नहीं करता है।

इसी तरह के और पेपर