Acyclic Dichromatic Number of Tournaments: these are the Champions

तकनीकी सारांश: टूर्नामेंट का अचक्रीय द्वि chromatic संख्या (Acyclic Dichromatic Number)

समस्या विवरण
यह शोध पत्र उन्मुख ग्राफ़ (oriented graphs) के 'अचक्रीय द्विchromatic संख्या' ($\vec{\chi}_a$) की जांच करता है, विशेष रूप से टूर्नामेंटों के संदर्भ में। एक अचक्रीय $k$-डाइकोलरिंग (acyclic $k$-dicolouring) शीर्षों का ऐसा $k$ सेटों में विभाजन है जहाँ किसी भी एकल भाग द्वारा प्रेरित उप-ग्राफ अचक्रीय होता है, और किन्हीं दो भागों के बीच का उन्मुख द्विपक्षीय ग्राफ (oriented bipartite graph) भी अकल्रीय होता है। अचक्रीय द्विchromatic संख्या ऐसे विभाजन के लिए आवश्यक न्यूनतम $k$ है।

लेखक बैंग-जेन्सेन, पिकासरी-एरिटा और येओ [4] द्वारा प्रस्तावित दो विशिष्ट अनुमानों को संबोधित करते हैं:

1. चैंपियंस का अभिलक्षण (Characterization of Champions): यह पहचानना कि कौन से टूर्नामेंट $H$ "चैंपियन" हैं (मानक डाइक्रोमैटिक संख्या सिद्धांत में "हीरोज़" के समान), जिसका अर्थ है कि प्रत्येक $H$-मुक्त टूर्नामेंट की अचक्रीय द्विchromatic संख्या सीमित होती है।
2. स्थानीय-से-वैश्विक गुण (Local-to-Global Property): यह निर्धारित करना कि क्या किसी टूर्नामेंट की अचक्रीय द्विchromatic संख्या उसके शीर्षों के आउट-नेबरहुड (out-neighborhoods) की अधिकतम अचक्रीय द्विchromatic संख्या के फलन (function) द्वारा सीमित है।

कार्यप्रणाली (Methodology)
शोध पत्र संरचनात्मक ग्राफ़ सिद्धांत और रैमसे-टाइप तर्कों का उपयोग करके अचक्रीय द्विchromatic संख्या पर सीमाएँ स्थापित करने के लिए काम करता है।

• डिमैचिंग (Dimatchings): एक केंद्रीय उपकरण जिसे 'डिमैचिंग' कहा गया है, उसे युग्मवार विलगित चापों (pairwise disjoint arcs) $\{a_1b_1, \dots, a_kb_k\}$ के रूप में परिभाषित किया गया है जहाँ यदि $i=j$ तो $a_i \to b_j$ और यदि $i \neq j$ तो $a_i \leftarrow b_j$ हो। लेखक इस परिणाम का लाभ उठाते हैं जो बैंग-जेन्सेन आदि [4] द्वारा दिया गया था, जिसके अनुसार बड़े डिमैचिंग का अस्तित्व उच्च अचक्रीय द्विchromatic संख्या को दर्शाता है।
• रैमसे थ्योरी (Ramsey Theory): प्रमाण बड़े टर्नमेंटों के भीतर विशिष्ट संरचनात्मक कॉन्फ़िगरेशन (विशेष रूप से, टूर्नामेंट $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$) खोजने के लिए एर्डोस-मोसर प्रमेय [8] का उपयोग करता है, जो बड़े टूर्नामेंटों में ट्रांज़िटिव सबटूर्नामेंट्स के अस्तित्व के संबंध में है।
• द्विपक्षीय ग्राफ़ में न्यूनीकरण (Reduction to Bipartite Graphs): उच्च अचक्रीय द्विchromatic संख्या वाले टूर्नामेंटों में बड़े डिमैचिंग्स के अस्तित्व को सिद्ध करने के लिए, लेखक समस्या को द्विपक्षीय ग्राफ़ के गुणों में कम करते हैं। वे बाइपार्टाइट ग्राफ़ में इंड्यूस्ड मैचिंग्स और को-मैचिंग्स के संबंध में एटमिनस [2] के परिणाम का उपयोग करते हैं। विशेष रूप से, वे बाइपार्टाइट टूर्नामेंट की अचक्रीय द्विchromatic संख्या को अंतर्निहित अनड्राइव्ड बाइपार्टाइट ग्राफ़ में प्रेरित $2K_2$ (इंड्यूस्ड मैचिंग्स का आकार 2) की अनुपस्थिति से जोड़ते हैं।
• पुनरावर्ती विभाजन (Recursive Partitioning): प्रमाणों में ट्रांज़िटिव सेटों में टूर्नामेंटों को विभाजित करना शामिल है और लेम्मा 9 से प्राप्त सहसंबंधों का उपयोग करके इन सेटों के बीच होने वाली परस्पर क्रियाओं का विश्लेषण करना शामिल है, जो एक डिपोग्राफ की अचकली द्विchromatic संख्या को नियंत्रित करता है।

मुख्य योगदान और परिणाम

1. चैंपियन अनुमान की पुष्टि (थ्योरम 3):
   लेखक सिद्ध करते हैं कि एक टूर्नामेंट $H$ चैंपियन है यदि और केवल यदि वह किसी पूर्णांक $k \ge 1$ के लिए $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ के सबटूर्नामेंट के आइसोमॉर्फिक (isomorphic) है।

   • तंत्र: वे प्रदर्शित करते हैं कि कोई भी टूर्नामेंट जिसमें पर्याप्त बड़ा डिमैचिंग है, उसमें $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ के आइसोमॉर्फिक सबटूर्नामेंट होगा। चूंकि बड़े डिमैचिंग उच्च अचक्रीय द्विchromatic संख्या को मजबूर करते हैं, इसलिए इस विशिष्ट संरचना से बचने वाला कोई भी टूर्नामेंट सीमित अचक्रीय द्विchromatic संख्या रखेगा।

2. डिमैचिंग्स का अस्तित्व (थ्योरम 4):
   शोध पत्र एक फलन $f: \mathbb{N} \to \mathbb{N}$ स्थापित करता है ताकि प्रत्येक टूर्नामेंट जिसकी अचक्रीय द्विchromatic संख्या कम से कम $f(k)$ है, उसमें आकार $k$ का एक डिमैचिंग मौजूद हो।

   • तंत्र: यह परिणाम बाइपार्टाइट ग्राफ़ के संबंध में एटमिनस के प्रमेय [2] पर निर्भर करता। यह दिखाते हुए कि यदि एक टूर्नामेंट में बड़ा डिमैचिंग नहीं है, तो उसकी संरचना को विशिष्ट बाइपार्टाइट इंटरैक्शन के साथ सीमित संख्या में ट्रांज़िटिव सेटों में विभाजित किया जा सकता है, लेखक अचक्रीय द्विchromatic संख्या को सीमित करते हैं।

3. स्थानीय-से-वैश्विक गुण की पुष्टि (थ्योरम 5):
   लेखक एक फलन $g: \mathbb{N} \to \mathbb{N}$ के अस्तित्व को सिद्ध करते हैं कि किसी भी टूर्नामेंट $T$ के लिए, $\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$।

   • तंत्र: इसे थ्योरम 4 के परिणाम के रूप में निकाला गया है। यदि किसी टूर्नामेंट की अचक्रीय द्विchromatic संख्या बड़ी है, तो इसमें एक बड़ा डिमैचिंग होता है। इस डिमैचिंग की संरचना यह सुनिश्चित करती है कि कुछ शीर्षों के आउट-नेबरहुड में एक बड़ा डिमैचिंग मौजूद है, जिससे स्थानीय नेबरहुड में उच्च अचक्रीय द्विchromatic संख्या अनिवार्य हो जाती है।

महत्ता और दावे
यह शोध पत्र बैंग-जेन्सेन, पिकासरी-एरिटा और येओ [4] के दो अनुमानों की पुष्टि करता है, जिससे अचक्रीय द्विchromatic संख्या के लिए "चैंपियंस" का लक्षण वर्णन पूर्ण होता है और इसका स्थानीय-से-वैश्विक गुण स्थापित होता है।

लेखक नोट करते हैं कि जबकि चैंपियन लक्षण वर्णन का अग्रिम निहितार्थ (कि चैंपियनों को उस विशिष्ट रूप में होना चाहिए) पहले से ज्ञात था, इस कार्य का नया योगदान इसका प्रतिलोम (converse) है—अर्थात, इस रूप के टूर्नामेंट वास्तव में चैंपियन हैं। इसके अतिरिक्त, पेपर परिशिष्ट में थ्योरम 3 के लिए एक वैकल्पिक प्रमाण प्रदान करता है जो थ्योरम 4 या एटमिनस के परिणाम पर निर्भर नहीं करता है, जिसे लेखक बेहतर ऊपरी सीमाओं (upper bounds) के रूप में देखते हैं और जिनका भविष्य के अनुसंधान के लिए स्वतंत्र महत्व हो सकता है।

यह कार्य गैप को पाटता है जो अच्छी तरह से समझे गए डाइक्रोमैटिक नंबर (जहाँ "हीरोज़" एक विशिष्ट पुनरावर्ती संरचना द्वारा वर्णित होते हैं) और अधिक प्रतिबंधात्मक अचक्रीय द्विchromatic नंबर के बीच है, यह दर्शाते हुए कि हालांकि संरचनाएं भिन्न हैं, टूर्नामेंटों में मौलिक गुण जैसे कि परिबद्धता (boundedness) और स्थानीयता दोनों मापदंडों के लिए लागू होते हैं।