🔢 mathematics

Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings

यह शोध पत्र सभी $k \ge 1$ और $t \ge 2$ के लिए $k$ विलगित 3-शीर्ष पथों और $t$ विलगित किनारों (जहाँ $n=3k+2t$ ) से बने स्पैनिंग लीनियर फॉरेस्ट्स के लिए एंटी-रैम्से नंबर निर्धारित करता है, जिससे पूर्ववर्ती कार्यों में मौजूद प्रतिबंधों के बिना इस समस्या का समाधान होता है।

मूल लेखक: Ali Ghalavand, Xueliang Li

प्रकाशित 2026-05-14✓ Author reviewed ⓘ

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

CC BY 4.0

मूल लेखक: Ali Ghalavand, Xueliang Li

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

कल्पना कीजिए कि आपके पास बहुत सारे मेहमानों वाली एक विशाल पार्टी है। आइए मेहमानों की कुल संख्या को $n$ कहें। इस पार्टी में, प्रत्येक अतिथि अन्य प्रत्येक अतिथि से ठीक एक बार हाथ मिलाता है। गणित के शब्दों में, यह एक "पूर्ण ग्राफ" (complete graph - $K_n$ ) है।

अब, कल्पना कीजिए कि आप पार्टी प्लानर हैं और आपके पास रंगीन मार्करों का एक बड़ा डिब्बा है। आपका काम हर एक हाथ मिलाने (एज/edge) को एक विशिष्ट रंग से रंगना है। आप पार्टी को जितना संभव हो सके उतना रंगीन बनाना चाहते हैं, लेकिन आपका एक सख्त नियम है: आपको एक विशिष्ट "इंद्रधनुषी पैटर्न" (rainbow pattern) बनाने से बचना है।

वर्जित पैटर्न (The Forbidden Pattern)

वह पैटर्न जिसे आप टालने की कोशिश कर रहे हैं, लोगों के छोटे, अलग-थलग समूहों का एक संग्रह है:

तीन लोगों के $k$ समूह जो एक रेखा में खड़े हैं (एक पथ या $P_3$ )।
दो लोगों के $t$ जोड़े जो एक साथ खड़े हैं (एक मिलान या $P_2$ )।

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

मुख्य प्रश्न

पेपर यह पूछता है: पार्टी के सभी हाथ मिलाने वाले हिस्सों को पेंट करने के लिए आप अधिकतम कितने अलग-अलग रंगों का उपयोग कर सकते हैं बिना अनजाने में इस वर्जित इंद्रधनुषी पैटर्न को बनाए रखे?

गणित की दुनिया में, इस अधिकतम संख्या को एंटी-रामेसे नंबर (Anti-Ramsey Number) कहा जाता है।

पिछला संघर्ष

लंबे समय तक, गणितज्ञों को इस प्रश्न का उत्तर पता था, लेकिन बहुत सख्त शर्तों के तहत। यह कुछ ऐसा था जैसे यह कहना कि, "हमें उत्तर पता है यदि जोड़ों की संख्या ( $t$ ) ट्रिपलेट्स ( $k$ ) की तुलना में बहुत बड़ी है।" विशेष रूप से, पिछले शोध के लिए आवश्यक था कि $t$ , $k$ के वर्ग (quadratic relationship) के बराबर हो। यदि $t$ उससे छोटा था, तो गणित काम नहीं करता था और उत्तर अज्ञात था।

नई खोज

यह पेपर सबसे महत्वपूर्ण और कठिन परिदृश्य के लिए इस पहेली को हल करता है: "स्पैनिंग केस" (The Spanning Case)।

"स्पैनिंग केस" को ऐसे समझें जैसे कि पार्टी पूरी तरह से भरी हुई है। मेहमानों की कुल संख्या ( $n$ ) ठीक उतनी ही है जितनी आपके वर्जित पैटर्न को बनाने के लिए लोगों की आवश्यकता है:

$n = 3 \times (\text{ट्रिपलेट्स की संख्या}) + 2 \times (\text{जोड़ों की संख्या})$
$n = 3k + 2t$

लेखक, अली घालवंद (Ali Ghalavand) और ज़ुएलियांग ली (Xueliang Li) ने सिद्ध किया कि अब आपको $t$ को बहुत बड़ा होने की आवश्यकता नहीं है। जब तक आपके पास कम से कम एक ट्रिपलेट ( $k \ge 1$ ) और कम से कम दो जोड़े ( $t \ge 2$ ) हैं, उन्होंने इस अधिकतम रंगों की संख्या के लिए सटीक सूत्र खोज लिया है।

सूत्र (The Formula)

पेपर दावा करता है कि आप उपयोग कर सकने वाले रंगों की अधिकतम संख्या है:
$\frac{1}{2}(3k + 2t - 3)(3k + 2t - 4) + 1$

साधारण अंग्रेजी (हिंदी) में इसका क्या अर्थ है?
यदि आप इस संख्या से एक अधिक रंग का उपयोग करने का प्रयास करते हैं, तो आप गणितीय रूप से गारंटी के साथ उस वर्जित इंद्रधनुषी पैटर्न को अनजाने में बना देंगे (वे $k$ ट्रिपलेट्स और $t$ जोड़े जिनमें सभी अद्वितीय रंग हैं)। लेकिन यदि आप इस संख्या या इससे कम रंगों का पालन करते हैं, तो आप रंगों को इस तरह व्यवस्थित कर सकते हैं कि पैटर्न कभी दिखाई न दे।

उन्होंने इसे कैसे सिद्ध किया

लेखकों ने एक चतुर "विभाजन और विजय" (divide and conquer) रणनीति का उपयोग किया, जिसे उन्होंने 16 अलग-अलग परिदृश्यों (जैसे कि रंगों को व्यवस्थित करने के हर संभावित तरीके की जाँच करना) में विभाजित किया:

निचली सीमा (The Lower Bound - "सुरक्षित तरीका"): उन्होंने दिखाया कि वे सूत्र के अनुसार रंगों के साथ ग्राफ को रंग सकते हैं जिससे पैटर्न नहीं बनता। कल्पना कीजिए कि आप पार्टी का एक बड़ा हिस्सा लेते हैं, उसे सभी अद्वितीय रंगों से रंगते हैं, और फिर शेष सभी हाथ मिलाने वाले हिस्सों को केवल एक नए रंग से पेंट करते हैं। यह किसी भी संभावित इंद्रधनुषी पैटर्न को तोड़ देता है क्योंकि "अतिरिक्त" हाथ मिलाने वाले हिस्से एक ही रंग साझा करते हैं।
ऊपरी सीमा (The Upper Bound - "खतरनाक तरीका"): उन्होंने सिद्ध किया कि यदि आप एक भी अधिक रंग का उपयोग करने का प्रयास करते हैं, तो आप पैटर्न बनाने के लिए मजबूर हो जाते हैं। उन्होंने यह मानकर कि आपने पैटर्न नहीं बनाया है और फिर यह दिखाकर कि यह गणितीय रूप से एक विरोधाभास (जैसे कि गोल छेद में चौकोर खूँटा फिट करने की कोशिश करना) की ओर ले जाता है। उन्होंने "अतिरिक्त" मेहमानों (मुख्य समूह में शामिल न होने वाले 3 लोग) के बीच रंगों के वितरण के हर संभावित तरीके का विश्लेषण किया और दिखाया कि चाहे कुछ भी हो, पैटर्न अंततः उभर कर आएगा।

निचोड़ (The Bottom Line)

यह पेपर "क्वाड्रेटिक लोअर बाउंड" (quadratic lower bound) की प्रतिबंध को हटा देता है। यह हमें बताता है कि विशेष मामले के लिए जहाँ पार्टी का आकार वर्जित पैटर्न के आकार के बिल्कुल बराबर है, उत्तर सरल और सार्वभौमिक है, चाहे आपके पास कितने भी ट्रिपलेट्स या जोड़े हों। यह ग्राफ थ्योरी के क्षेत्र में एक विशिष्ट, कठिन पहेली का पूर्ण समाधान है।

तकनीकी सारांश: 3-शीर्ष वाले पथों और मिलान (matchings) के लिए स्पैनिंग लीनियर फॉरेस्ट के एंटी-रैम्से नंबर

समस्या विवरण
यह शोध पत्र $K_n$ के पूर्ण ग्राफ (complete graph) में एक विशिष्ट प्रकार के लीनियर फॉरेस्ट के लिए एंटी-रैम्से नंबर, जिसे $AR(n, G)$ द्वारा दर्शाया गया है, की जांच करता है। एक उपग्राफ (subgraph) को रेनबो (rainbow) तब कहा जाता है जब उसके सभी किनारों (edges) के रंग भिन्न होते हैं। एंटी-रैम्से नंबर $AR(n, G)$, $K_n$ के एज-कलरिंग में रंगों की वह अधिकतम संख्या है जो $G$ की एक रेनबो प्रति (rainbow copy) होने से बचती है।

अध्ययन के अंतर्गत विशिष्ट ग्राफ $G$ , लीनियर फॉरेस्ट $kP_3 \cup tP_2$ है, जिसमें $k$ अलग-अलग पथ (प्रत्येक की लंबाई 2, यानी 3 शीर्ष) और एक मिलान (matching) आकार $t$ (अलग-अलग किनारे) शामिल हैं। मुख्य ध्यान स्पैनिंग केस (spanning case) पर है, जहाँ होस्ट ग्राफ के शीर्षों की संख्या फॉरेस्ट के शीर्षों की संख्या के बराबर होती है, अर्थात $n = 3k + 2t$ । जबकि पिछले साहित्य में $k \ge 2$ के लिए $t$ पर प्रतिबंधात्मक शर्तों (विशेष रूप से $t \ge \frac{k^2-3k+4}{2}$ ) के तहत इस समस्या को संबोधित किया गया था, यह कार्य $k \ge 1$ और $t \ge 2$ के लिए बिना किसी अतिरिक्त प्रतिबंध के स्पैनिंग केस को हल करने का लक्ष्य रखता है।

कार्यप्रणाली
मुख्य प्रमेय का प्रमाण इंडक्शन (induction) और एज-कलरिंग के विस्तृत केस विश्लेषण के संयोजन पर आधारित है। कार्यप्रणाली को निम्नानुसार संरचित किया गया है:

इंडक्टिव फ्रेमवर्क (Inductive Framework): प्रमाण $k$ पर इंडक्शन द्वारा आगे बढ़ता है। बेस केस $k=1$ को हे और जिन (He and Jin) के एक ज्ञात परिणाम का उपयोग करके स्थापित किया गया है जो $AR(n, P_3 \cup tP_2)$ के लिए है।
प्रमुख लेम्मा (Lemma 2.2): रिडक्शन स्टेप (reduction step) को संभालने के लिए एक महत्वपूर्ण लेम्मा स्थापित किया गया है। यह दावा करता है कि यदि $K_n$ का एक एज-कलरिंग पर्याप्त संख्या में रंगों (विशेष रूप से $\frac{1}{2}(3k+2t-3)(3k+2t-4)+2$ ) को समाहित करता है, तो एक उपग्राफ $K_{n-3}$ (तीन शीर्षों को हटाने से प्राप्त) मौजूद होता है जो उच्च रंग घनत्व (जैसे कम से कम $\frac{1}{2}(3(k-1)+2t-3)(3(k-1)+2t-4)+2$ विशिष्ट रंग) बनाए रखता है। यह $K_{n-3}$ के भीतर एक रेनबो $(k-1)P_3 \cup tP_2$ खोजने के लिए इंडक्टिव हाइपोथीसिसिस (inductive hypothesis) को लागू करने की अनुमति देता है।
व्यापक परिदृश्य विश्लेषण (Exhaustive Scenario Analysis): इंडक्शन को पूरा करने के लिए, लेखक हटाए गए शीर्षों के सेट $S = \{s_1, s_2, s_3\}$ $S = {s_{1}, s_{2}, s_{3}}$ और शेष ग्राफ के बीच के किनारों और $S$ $S$ के भीतर के किनारों को दिए गए रंगों का विश्लेषण करते हैं। प्रमाण $K_{n-3}$ $K_{n - 3}$ में एक रेनबो $(k-1)P_3 \cup tP_2$ $(k - 1) P_{3} \cup t P_{2}$ के अस्तित्व को मानता है और $S$ $S$ के किनारों के रंग वितरण और मौजूदा रेनबो उपग्राफ के साथ उनके इंटरसेक्शन के आधार पर 16 अलग-अलग परिदृश्यों (scenarios) का परीक्षण करता है।
- ये परिदृश्य विभिन्न कॉन्फ़िगरेशन को कवर करते हैं, जैसे कि क्या $S$ के किनारे नए रंग पेश करते हैं, मौजूदा उपग्राफ के रंगों को दोहराते हैं, या विशिष्ट रेनबो पथों ( $P_3$ ) या मिलान ( $P_2$ ) का निर्माण करते हैं, जिन्हें मौजूदा संरचना के साथ जोड़ा जा सकता है।
- प्रत्येक परिदृश्य के लिए, लेखक प्रदर्शित करते हैं कि यदि कुल रंगों की संख्या प्रस्तावित सीमा से अधिक है, तो एक रेनबो $kP_3 \cup tP_2$ का निर्माण किया जा सकता है।
- यदि ऐसा कोई निर्माण तुरंत संभव नहीं है, तो वे रेनबो उपग्राफ बनाने के लिए आवश्यक स्थितियों के न होने की धारणा के तहत, $K_n$ में रंगों की अधिकतम संख्या की गणना करके एक विरोधाभास (contradiction) उत्पन्न करते हैं। सभी मामलों में, यह ऊपरी सीमा (upper bound) मानी गई रंगों की संख्या से कम आती है, जिससे सिद्ध होता है कि एक रेनबो उपग्राफ अवश्य मौजूद होगा।

प्रमुख योगदान और परिणाम
यह शोध पत्र स्पैनिंग लीनियर फॉरेस्ट $kP_3 \cup tP_2$ के लिए एंटी-रैम्से नंबर का सटीक मान स्थापित करता है।

प्रमेय 1.1: धनात्मक पूर्णांकों $k \ge 1$ , $t \ge 2$ , और $n = 3k + 2t$ के लिए:
$AR(n, kP_3 \cup tP_2) = \frac{1}{2}(3k + 2t - 3)(3k + 2t - 4) + 1$

यह परिणाम पुष्टि करता है कि $K_n$ के कलरिंग में रंगों की अधिकतम संख्या, $n-3$ शीर्षों वाले पूर्ण ग्राफ के किनारों की संख्या से ठीक एक अधिक है। शोध पत्र एक मैचिंग लोअर बाउंड कंस्ट्रक्शन (एक $K_{n-3}$ उपग्राफ को विशिष्ट रंगों के साथ रंगना और शेष सभी किनारों को एक ही नए रंग को सौंपना) प्रदान करता है और ऊपर वर्णित विस्तृत केस विश्लेषण के माध्यम से ऊपरी सीमा (upper bound) को सिद्ध करता है।

महत्व
इस कार्य का महत्व पिछले अध्ययनों में आवश्यक $t$ के द्विघात निचली सीमा (quadratic lower bound) को हटाने में निहित है। विशेष रूप से, दो लेखकों के एक पूर्व परिणाम (संदर्भ [11] में) ने यह संख्या केवल $t \ge \frac{k^2-3k+4}{2}$ के लिए निर्धारित की थी। यह शोध पत्र सिद्ध करता है कि यह सूत्र $k$ के परिमाण के बावजूद सभी $t \ge 2$ के लिए मान्य है।

लेखक इसे "उस महत्वपूर्ण मामले के लिए पूर्ण लक्षण वर्णन (complete characterization) प्रदान करना कहते हैं जिसमें होस्ट ग्राफ में फॉरेस्ट के समान ही शीर्ष होते हैं।" पथ घटकों और मिलान घटकों के अनुपात पर प्रतिबंधों के बिना स्पैनिंग केस को हल करके, यह शोध पत्र लीनियर फॉरेस्ट के एंटी-रैम्से नंबरों की समझ में एक महत्वपूर्ण अंतराल को भरता है। लेखक उल्लेख करते हैं कि शेष खुला प्रश्न गैर-स्पैनिंग केस ( $n \ge 3k + 2t + 1$ ) के लिए है जब $t$ छोटा हो।