द्विपक्षीय तुरान संख्या पथ और अन्य वृक्षों की

मूल जानकारी

• पेपर ID: 2511.07374
• शीर्षक: द्विपक्षीय तुरान संख्या पथ और अन्य वृक्षों की
• लेखक: मार्थे बोनामी, थिओटाइम लेक्लेरे, तिमोथे पिकावेट
• संस्थान: CNRS, LaBRI, बोर्डो विश्वविद्यालय; ENS पेरिस-सैक्ले
• वर्गीकरण: math.CO (संयोजन गणित), cs.DM (असतत गणित)
• प्रकाशन तिथि: 11 नवंबर 2025
• पेपर लिंक: https://arxiv.org/abs/2511.07374

सारांश

यह पेपर कारो, पाटकोस और तुजा द्वारा हाल ही में प्रस्तुत एक समस्या को पूरी तरह से हल करता है: द्विपक्षीय जुड़े हुए ग्राफ में किनारों की सटीक अधिकतम संख्या निर्धारित करना, जो ग्राफ में सबसे लंबे पथ की लंबाई और द्विपक्षीय विभाजन के दोनों ओर शीर्षों की संख्या का एक कार्य है। पहले यह समस्या केवल तब ज्ञात थी जब द्विपक्षीय विभाजन के दोनों ओर का आकार समान हो और सबसे लंबे पथ की लंबाई अधिकतम 5 हो। यह पेपर "पथ" को विशिष्ट प्रकार के वृक्षों से बदलने के संभावित सामान्यीकरण पर भी चर्चा करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

1. शास्त्रीय तुरान समस्या: तुरान प्रमेय दिए गए क्रम के पूर्ण उप-ग्राफ को न रखने वाले n शीर्षों वाले ग्राफ की अधिकतम किनारों की संख्या निर्धारित करता है, जो निषिद्ध उप-ग्राफ चरम समस्याओं के व्यवस्थित अध्ययन को शुरू करता है।
2. एर्डोस-स्टोन प्रमेय की सीमाएं: यह प्रमेय सभी गैर-द्विपक्षीय निषिद्ध ग्राफों के तुरान संख्या को स्पर्शोन्मुख रूप से देता है, लेकिन द्विपक्षीय ग्राफ के मामले में कोई जानकारी नहीं देता है।
3. द्विपक्षीय ग्राफों की विशेषता: द्विपक्षीय ग्राफों की तुरान समस्या अभी भी खुली है, जिसने कई मुख्य अनुमानों को जन्म दिया है, सबसे प्रसिद्ध एर्डोस-सोस अनुमान है: k शीर्षों वाले वृक्ष को बाहर करने वाले n शीर्षों वाले ग्राफ में अधिकतम (k-2)n/2 किनारे हैं।
4. जुड़े हुए द्विपक्षीय ग्राफों का अध्ययन: कारो, पाटकोस और तुजा CPT25 ने हाल ही में उस स्थिति पर ध्यान केंद्रित किया जहां होस्ट ग्राफ द्विपक्षीय और जुड़ा हुआ दोनों है, संकेतन exb,c(a,b,H) को प्रस्तुत किया जो भाग के आकार a और b वाले जुड़े हुए द्विपक्षीय ग्राफों की अधिकतम किनारों की संख्या को दर्शाता है जो H को उप-ग्राफ के रूप में नहीं रखते हैं।

अनुसंधान की प्रेरणा

• ज्ञात परिणामों की सीमाएं: CPT25 ने केवल 6 या उससे कम शीर्षों वाले सभी वृक्षों, द्वितारों और कुछ मकड़ी ग्राफों के मामले को हल किया है, विशेष रूप से केवल exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1 ज्ञात है
• खुली समस्या: किसी भी पथ Pₖ के लिए exb,c(n,n,Pₖ) निर्धारित करने की आवश्यकता है, कम से कम स्पर्शोन्मुख मान दें
• सामान्यीकरण की आवश्यकता: विशिष्ट वृक्ष परिवारों के exb,c मानों का अध्ययन करने की आवश्यकता है

मुख्य योगदान

1. पथ समस्या का पूर्ण समाधान: सभी पथों Pₖ के लिए, exb,c(a,b,Pₖ) के सटीक मान दिए गए हैं, न केवल स्पर्शोन्मुख मान, बल्कि असंतुलित द्विपक्षीय ग्राफों के लिए भी लागू होते हैं (मुख्य प्रमेय 1.5)
2. झाड़ू ग्राफों तक विस्तार: झाड़ू ग्राफों Sp,d* (पथ लंबाई p और d शाखाओं वाले तारे का संयोजन) के लिए, जब तारा पथ से बड़ा हो तो सटीक मान दिए गए हैं (प्रमेय 1.6)
3. ऊपरी सीमा परिणाम: जब तारा पथ के आकार का अधिकतम आधा हो तो ऊपरी सीमा प्रदान की गई है (प्रमेय 1.7)
4. तकनीकी नवाचार: जुड़े हुए द्विपक्षीय ग्राफों को संभालने के लिए नई तकनीकें विकसित की गई हैं, जिनमें महत्वपूर्ण शीर्षों के अस्तित्व की लेम्मा और आगमनात्मक ढांचा शामिल है

विधि विवरण

कार्य परिभाषा

परिभाषा 1.1: निश्चित पूर्णांकों a, b और ग्राफ H के लिए, exb,c(a,b,H) भाग के आकार a और b वाले जुड़े हुए द्विपक्षीय ग्राफों की अधिकतम किनारों की संख्या है जो H को उप-ग्राफ के रूप में नहीं रखते हैं।

यह पेपर मुख्य रूप से अध्ययन करता है:

• इनपुट: पथ की लंबाई k, द्विपक्षीय विभाजन के आकार a, b
• आउटपुट: exb,c(a,b,Pₖ) का सटीक मान
• बाधाएं: ग्राफ जुड़ा हुआ, द्विपक्षीय और Pₖ को उप-ग्राफ के रूप में नहीं रखता है

मुख्य प्रमेय

प्रमेय 1.5 (मुख्य परिणाम): सभी k ≥ 3 और b ≥ a ≥ k के लिए, $\text{ex}_{b,c}(a,b,P_{2k}) = \text{ex}_{b,c}(a,b,P_{2k-1}) = (k-2)(b-1) + a$

यह सूत्र दर्शाता है:

• विषम और सम लंबाई के पथों की समान तुरान संख्या होती है
• किनारों की संख्या बड़े भाग b के साथ रैखिक रूप से बढ़ती है, गुणांक (k-2) के साथ
• एक योगात्मक सुधार पद a मौजूद है

प्रमाण आर्किटेक्चर

1. निचली सीमा निर्माण (अनुभाग 2)

प्रस्ताव 2.1 रचनात्मक प्रमाण प्रदान करता है:

एक ग्राफ G का निर्माण करें, जिसका द्विपक्षीय विभाजन A = {u₁,...,uₐ} और B = {v₁,...,vᵦ} है:

• A के पहले k-2 शीर्ष B के सभी शीर्षों से पूरी तरह जुड़े हैं (Kₖ₋₂,ᵦ बनाते हैं)
• A के शेष a-(k-2) शीर्ष पत्तियों के रूप में कार्य करते हैं, सभी B के एक विशिष्ट शीर्ष से जुड़े हैं

किनारों की गणना: $|E(G)| = b(k-2) + (a-(k-2)) = (k-2)(b-1) + a$

P₂ₖ₋₁-मुक्त संपत्ति का प्रमाण:

• पूर्ण द्विपक्षीय ग्राफ Kₖ₋₂,ᵦ का सबसे लंबा पथ 2k-3 शीर्षों वाला है
• जोड़े गए पत्तियां पथ को नहीं बढ़ा सकते, क्योंकि वे सभी डिग्री 1 के शीर्ष हैं

2. ऊपरी सीमा प्रमाण (अनुभाग 3)

आगमन का उपयोग करते हुए, मुख्य तीन लेम्मा हैं:

लेम्मा 3.2 (छोटी डिग्री शीर्षों का अस्तित्व): बड़े भाग B में डिग्री ≤ k-2 वाला एक शीर्ष x मौजूद है जिसे हटाने के बाद ग्राफ जुड़ा हुआ रहता है।

प्रमाण विचार:

• B में एक पत्ती b खोजने के लिए DFS वृक्ष का उपयोग करें
• यदि d(b) ≤ k-2, तो x = b लें
• यदि d(b) = k-1, तो पथ की लंबाई 2k-2 होनी चाहिए, एक चक्र बनाते हुए
• इस स्थिति में डिग्री ≤ k-2 वाला एक अन्य शीर्ष b' खोजें

लेम्मा 3.3 (संतुलित ग्राफों में हटाने योग्य शीर्षों की जोड़ी): संतुलित द्विपक्षीय ग्राफ के लिए, दो शीर्ष x, y मौजूद हैं जैसे कि d(x) + d(y) ≤ k-1 और हटाने के बाद ग्राफ जुड़ा हुआ और संतुलित रहता है।

प्रमाण सबसे लंबे पथ P के अंतबिंदुओं का विश्लेषण करता है:

• यदि अंतबिंदु विभिन्न भागों में हैं, तो सीधे उपयोग किया जा सकता है
• अन्यथा उपयुक्त पत्तियों की जोड़ी खोजने के लिए DFS वृक्ष का उपयोग करें

लेम्मा 3.4 (आधार स्थिति): जब a = b = k हो, तो |E(G)| ≤ (k-1)² + 1।

प्रमाण आगमन का उपयोग करता है, मुख्य अवलोकन:

• एक गैर-कट-बिंदु की न्यूनतम डिग्री वाला शीर्ष x खोजें
• x को हटाने के बाद शेष ग्राफ का विश्लेषण करें
• P₂ₖ-मुक्त संपत्ति का उपयोग करके डिग्री और संरचना को सीमित करें

मुख्य प्रमेय का प्रमाण:

• यदि b > a: लेम्मा 3.2 का उपयोग करके एक शीर्ष हटाएं, आगमन करें
• यदि a = b > k: लेम्मा 3.3 का उपयोग करके दो शीर्ष हटाएं, आगमन करें
• यदि a = b = k: लेम्मा 3.4 का उपयोग करें

झाड़ू ग्राफों के परिणाम

प्रमेय 1.6: k, d ≥ 2 के लिए, जब n ≥ d²/2 और d > 2k हो, तो $\text{ex}_{b,c}(n,n,S_{2k,d}) = \text{ex}_{b,c}(n,n,S_{2k+1,d}) = nd$

मुख्य तकनीकी लेम्मा:

लेम्मा 4.1: यदि ग्राफ में ऐसा शीर्ष मौजूद है जो 2k लंबाई के पथ का अंतबिंदु नहीं है, तो |E(G)| ≤ (k-1)(b+a)

लेम्मा 4.2: यदि |E(G)| ≥ k(b+a)+1, तो प्रत्येक शीर्ष की डिग्री अधिकतम k+d-1 है

प्रमाण इन लेम्मा को संयोजित करता है, अधिकतम डिग्री शीर्ष और इसके पड़ोसियों को हटाते हुए, जुड़ाव और डिग्री बाधाओं का उपयोग करके विरोधाभास प्राप्त करता है।

प्रायोगिक सेटअप

शुद्ध सैद्धांतिक गणित पेपर होने के नाते, इस पेपर में कोई प्रायोगिक भाग नहीं है, सभी परिणाम कठोर गणितीय प्रमाण के माध्यम से प्राप्त किए गए हैं।

प्रायोगिक परिणाम

मुख्य परिणामों का सत्यापन

पथों के लिए सटीक सूत्र:

• P₅ और P₆ के लिए: exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
  • सूत्र का उपयोग करते हुए: k=3 जब, (3-2)(n-1)+n = n-1+n = 2n-1 ✓
• सामान्य Pₖ के लिए: सूत्र सभी स्थितियों के लिए सटीक मान देता है, जिसमें असंतुलित द्विपक्षीय ग्राफ भी शामिल हैं

झाड़ू ग्राफ परिणाम:

• जब तारा भाग प्रमुख हो (d > 2k), तुरान संख्या nd है
• यह अधिकतम डिग्री बाधा के अनुरूप है

ज्ञात परिणामों के साथ तुलना

1. प्रस्ताव 1.2 का सामान्यीकरण: यह पेपर CPT25 में exb,c(n,n,P₅) = 2n-1 को पूरी तरह से शामिल करता है और सामान्य करता है
2. सामान्यता में वृद्धि:
   • संतुलित ग्राफों से असंतुलित ग्राफों तक विस्तार
   • विशिष्ट छोटे पथों से किसी भी पथ तक विस्तार
   • स्पर्शोन्मुख परिणामों से सटीक सूत्र तक

संबंधित कार्य

शास्त्रीय परिणाम

1. तुरान प्रमेय Tur45: पूर्ण ग्राफों की चरम समस्या
2. एर्डोस-स्टोन प्रमेय ES46: गैर-द्विपक्षीय ग्राफों की स्पर्शोन्मुख तुरान संख्या
3. गैलाई-एर्डोस GE59: निश्चित आकार के पथों को बाहर करने वाले जुड़े हुए ग्राफों के स्पर्शोन्मुख परिणाम
4. ग्यारफास-रूसो-शेल्प GRS84: निश्चित आकार के पथों को बाहर करने वाले द्विपक्षीय ग्राफों की सटीक तुरान संख्या

सीधे संबंधित कार्य

कारो-पाटकोस-तुजा CPT25:

• exb,c संकेतन को प्रस्तुत किया
• छोटे वृक्षों के मामले को हल किया (≤6 शीर्ष)
• द्वितारों और कुछ मकड़ी ग्राफों को हल किया
• इस पेपर द्वारा हल की गई समस्या को प्रस्तुत किया

स्वतंत्र कार्य

हे-सालिया-झु HSZ25: लेखकों ने उल्लेख किया कि उसी दिन समान प्रगति के साथ स्वतंत्र कार्य प्रस्तुत किया गया था

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. प्रश्न 1.3 का पूर्ण उत्तर: सभी पथों Pₖ के लिए exb,c(n,n,Pₖ) के सटीक मान दिए गए हैं, जो प्रश्न द्वारा आवश्यक स्पर्शोन्मुख मानों से अधिक है
2. प्रश्न 1.4 का आंशिक उत्तर: झाड़ू ग्राफ परिवार के लिए, विशिष्ट पैरामीटर श्रेणियों में सटीक मान या ऊपरी सीमाएं दी गई हैं
3. पद्धति संबंधी योगदान: जुड़े हुए द्विपक्षीय ग्राफ चरम समस्याओं को संभालने के लिए नई तकनीकी ढांचा विकसित किया गया है

सीमाएं

1. झाड़ू ग्राफों की सीमाएं:
   • प्रमेय 1.6 को d > 2k और n ≥ d²/2 की आवश्यकता है
   • प्रमेय 1.7 केवल ऊपरी सीमा देता है, सटीक मान नहीं
   • मध्यवर्ती स्थिति (d ≈ k) पूरी तरह से हल नहीं है
2. वृक्षों का सामान्य मामला: केवल पथों और झाड़ू ग्राफों को संभाला गया है, अधिक सामान्य वृक्ष परिवार अभी भी खुले हैं
3. तकनीकी सीमाएं: कुछ प्रमाण चरण विशिष्ट संरचनात्मक गुणों पर निर्भर करते हैं, जो अधिक जटिल निषिद्ध उप-ग्राफों तक सामान्यीकृत करना मुश्किल हो सकता है

भविष्य की दिशाएं

1. झाड़ू ग्राफ परिणामों को परिष्कृत करना: सभी पैरामीटर श्रेणियों के लिए सटीक मान निर्धारित करना
2. अन्य वृक्ष परिवारों तक विस्तार:
   • मकड़ी ग्राफों का पूर्ण लक्षण वर्णन
   • अन्य विशेष वृक्ष संरचनाएं
3. असंतुलित स्थिति का गहन अध्ययन: हालांकि यह पेपर a ≠ b के मामले को संभालता है, लेकिन अधिक सूक्ष्म परिणाम संभव हो सकते हैं
4. कम्प्यूटेशनल जटिलता: यह अध्ययन करना कि दिया गया ग्राफ तुरान सीमा को प्राप्त करता है या नहीं, इसे निर्धारित करने की एल्गोरिथम समस्या

गहन मूल्यांकन

शक्तियां

1. खुली समस्या का पूर्ण समाधान:
   • न केवल प्रश्न 1.3 का उत्तर देता है, बल्कि आवश्यकता से अधिक मजबूत सटीक सूत्र देता है
   • असंतुलित द्विपक्षीय ग्राफों तक विस्तारित, परिणामों की सामान्यता को बढ़ाता है
2. प्रमाण तकनीकें सुंदर हैं:
   • निचली सीमा निर्माण सरल और स्पष्ट है
   • ऊपरी सीमा प्रमाण की आगमनात्मक संरचना स्पष्ट है
   • मुख्य लेम्मा (3.2, 3.3, 3.4) के कथन और प्रमाण दोनों ही परिष्कृत हैं
3. परिणामों की पूर्णता:
   • पथों के लिए, सभी पैरामीटरों के लिए सटीक सूत्र दिए गए हैं
   • सूत्र रूप सरल है: (k-2)(b-1)+a
   • विषम और सम लंबाई के पथों को एकीकृत रूप से संभाला गया है
4. लेखन की गुणवत्ता:
   • पेपर संरचना स्पष्ट, तर्क कठोर है
   • मुख्य चरणों में विस्तृत उप-प्रस्ताव हैं
   • चित्र (जैसे चित्र 1) निर्माण को समझने में मदद करते हैं
5. तकनीकी नवाचार:
   • लेम्मा 3.2 छोटी डिग्री वाले गैर-कट-बिंदुओं के अस्तित्व के बारे में मुख्य अंतर्दृष्टि है
   • संतुलित ग्राफों में हटाने योग्य शीर्षों की जोड़ी का लक्षण वर्णन (लेम्मा 3.3) स्वतंत्र मूल्य रखता है

• DFS वृक्ष का उपयोग पूरे प्रमाण में होता है, शास्त्रीय उपकरणों के प्रभावी अनुप्रयोग को दर्शाता है

कमियां

1. झाड़ू ग्राफ परिणाम अधूरे हैं:
   • प्रमेय 1.6 और 1.7 के बीच पैरामीटर अंतराल मौजूद है
   • प्रमेय 1.7 केवल ऊपरी सीमा 2nk+1 देता है, संभावित सटीक मान से अंतर अज्ञात है
   • शर्त n ≥ d²/2 तकनीकी रूप से मजबूत लगती है, संभवतः इष्टतम नहीं है
2. आधार स्थिति का प्रमाण जटिल है:
   • लेम्मा 3.4 (a=b=k की स्थिति) का प्रमाण काफी स्थान लेता है
   • कई उप-प्रस्तावों (दावे 3.11-3.13) की आवश्यकता है
   • अधिक प्रत्यक्ष तर्क संभव हो सकता है
3. सामान्यीकरण की सीमित क्षमता:
   • विधि पथों और झाड़ू ग्राफों की विशेष संरचना पर अत्यधिक निर्भर है
   • सामान्य वृक्षों के लिए, इन तकनीकों को कैसे लागू किया जाए यह स्पष्ट नहीं है
   • संभावित एकीकृत ढांचे पर चर्चा नहीं की गई है
4. स्वतंत्र कार्य के साथ संबंध:
   • HSZ25 के स्वतंत्र कार्य का उल्लेख किया गया है लेकिन विस्तार से तुलना नहीं की गई है
   • दोनों पेपरों की तकनीकी विधियां समान हैं या नहीं यह स्पष्ट नहीं है

प्रभाव

1. सैद्धांतिक योगदान:
   • एक स्पष्ट रूप से प्रस्तुत खुली समस्या को पूरी तरह से हल करता है
   • जुड़े हुए द्विपक्षीय तुरान समस्या के लिए नई तकनीकी उपकरण प्रदान करता है
   • परिणामों की सटीकता इसे इस क्षेत्र के लिए एक बेंचमार्क बनाती है
2. पद्धति संबंधी मूल्य:
   • आगमनात्मक ढांचा अन्य निषिद्ध उप-ग्राफ समस्याओं पर लागू हो सकता है
   • मुख्य लेम्मा अन्य संदर्भों में उपयोगी हो सकते हैं
3. अनुवर्ती अनुसंधान:
   • स्वाभाविक रूप से झाड़ू ग्राफों के पूर्ण लक्षण वर्णन की समस्या को जन्म देता है
   • अन्य वृक्ष परिवारों के exb,c मानों का अध्ययन करने के लिए प्रेरित करता है
   • गैर-जुड़े हुए मामले के अनुसंधान को प्रेरित कर सकता है
4. सत्यापनीयता:
   • शुद्ध सैद्धांतिक परिणाम होने के नाते, प्रमाण की जांच करके सत्यापित किया जा सकता है
   • निर्माण स्पष्ट है, समझने और सत्यापित करने में आसान है
   • सूत्र सरल है, अनुप्रयोग और उद्धरण के लिए सुविधाजनक है

प्रयोज्य परिदृश्य

1. सैद्धांतिक अनुसंधान:
   • चरम ग्राफ सिद्धांत शोधकर्ताओं के लिए संदर्भ परिणाम
   • तुरान प्रकार की समस्याओं के लिए तकनीकी स्रोत
   • जुड़ाव बाधा के तहत चरम समस्याओं का केस अध्ययन
2. संबंधित समस्याएं:
   • एर्डोस-सोस अनुमान के अनुसंधान के लिए संभावित रूप से प्रेरणादायक
   • अन्य वृक्षों की तुरान संख्या के लिए तुलना प्रदान करता है
   • जुड़े हुए द्विपक्षीय ग्राफों की संरचनात्मक गुणों का अनुसंधान
3. शिक्षण मूल्य:
   • चरम संयोजन में आगमन विधि के अनुप्रयोग को दर्शाता है
   • DFS वृक्ष और पथ विश्लेषण का उदाहरण
   • ऊपरी और निचली सीमा मिलान का पूर्ण केस

संदर्भ (मुख्य साहित्य)

1. CPT25 कारो, पाटकोस, तुजा: वृक्षों की द्विपक्षीय तुरान संख्या - इस पेपर द्वारा हल की गई समस्या को प्रस्तुत करता है
2. Tur45 तुरान: ग्राफ सिद्धांत में एक चरम समस्या पर - तुरान समस्या की नींव रखता है
3. ES46 एर्डोस, स्टोन: रैखिक ग्राफों की संरचना पर - एर्डोस-स्टोन प्रमेय
4. GRS84 ग्यारफास, रूसो, शेल्प: द्विपक्षीय ग्राफों में पथों के लिए एक चरम समस्या - द्विपक्षीय ग्राफों में पथों की सटीक तुरान संख्या (जुड़ाव की आवश्यकता के बिना)
5. HSZ25 हे, सालिया, झु: लंबे चक्रों और पथों के लिए जुड़ी हुई द्विपक्षीय तुरान समस्या - स्वतंत्र संबंधित कार्य

समग्र मूल्यांकन

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