2025-11-10T03:03:05.603358

Rainbow triangles sharing one common vertex or edge

Chen, Ning
Let $G$ be an edge-colored graph on $n$ vertices. For a vertex $v$, the \emph{color degree} of $v$ in $G$, denoted by $d^c(v)$, is the number of colors appearing on the edges incident with $v$. Denote by $δ^c(G)=\min\{d^c(v):v\in V(G)\}$. By a theorem of H. Li, an $n$-vertex edge-colored graph $G$ contains a rainbow triangle if $δ^c(G)\geq \frac{n+1}{2}$. Inspired by this result, we consider two related questions concerning edge-colored books and friendship subgraphs of edge-colored graphs. Let $k\geq 2$ be a positive integer. We prove that if $δ^c(G)\geq \frac{n+k-1}{2}$ where $n\geq 3k-2$, then $G$ contains $k$ rainbow triangles sharing one common edge; and if $δ^c(G)\geq \frac{n+2k-3}{2}$ where $n\geq 2k+9$, then $G$ contains $k$ rainbow triangles sharing one common vertex. The special case $k=2$ of both results improves H. Li's theorem. The main novelty of our proof of the first result is a combination of the recent new technique for finding rainbow cycles due to Czygrinow, Molla, Nagle, and Oursler and some recent counting technique from \cite{LNSZ}. The proof of the second result is with the aid of the machine implicitly in the work of Turán numbers for matching numbers due to Erdős and Gallai.
academic

एक सामान्य शीर्ष या किनारे को साझा करने वाले इंद्रधनुष त्रिभुज

मूल जानकारी

  • पेपर ID: 2302.00851
  • शीर्षक: Rainbow triangles sharing one common vertex or edge
  • लेखक: Xiaozheng Chen (郑州大学), Bo Ning (南开大学)
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 2 फरवरी 2023 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2302.00851

सारांश

यह पेपर किनारे-रंगीन ग्राफ़ में इंद्रधनुष त्रिभुजों के अस्तित्व की समस्या का अध्ययन करता है। nn शीर्षों वाले किनारे-रंगीन ग्राफ़ GG के लिए, शीर्ष vv की रंग-डिग्री dc(v)d^c(v) को vv से सटे किनारों द्वारा उपयोग किए जाने वाले विभिन्न रंगों की संख्या के रूप में परिभाषित किया जाता है। न्यूनतम रंग-डिग्री को δc(G)=min⁡{dc(v):v∈V(G)}\delta^c(G)=\min\{d^c(v):v\in V(G)\} के रूप में दर्शाया जाता है। H. Li की प्रमेय दर्शाती है कि जब δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2} हो, तो ग्राफ़ GG में इंद्रधनुष त्रिभुज होता है। इससे प्रेरित होकर, लेखकों ने किनारे-रंगीन ग्राफ़ में बुक ग्राफ़ (books) और मित्रता ग्राफ़ (friendship graphs) संरचनाओं का अध्ययन किया। मुख्य परिणाम प्रमाणित करते हैं: जब δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} और n≥3k−2n\geq 3k-2 हो, तो GG में kk इंद्रधनुष त्रिभुज होते हैं जो एक किनारे को साझा करते हैं; जब δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} और n≥2k+9n\geq 2k+9 हो, तो GG में kk इंद्रधनुष त्रिभुज होते हैं जो एक शीर्ष को साझा करते हैं।

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

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

  1. शास्त्रीय त्रिभुज समस्या: Mantel (1907) ने प्रमाणित किया कि nn शीर्षों वाले त्रिभुज-मुक्त ग्राफ़ में अधिकतम ⌊n24⌋\lfloor\frac{n^2}{4}\rfloor किनारे होते हैं
  2. संरचित त्रिभुज: Erdős आदि ने बुक ग्राफ़ BkB_k (एक किनारे को साझा करने वाले kk त्रिभुज) और मित्रता ग्राफ़ FkF_k (एक शीर्ष को साझा करने वाले kk त्रिभुज) की Turán संख्याओं का अध्ययन किया
  3. इंद्रधनुष उप-ग्राफ़: इंद्रधनुष उप-ग्राफ़ और सही रंगीन उप-ग्राफ़ कई ग्राफ़ सिद्धांत गुणों से निकटता से संबंधित हैं, जैसे शास्त्रीय स्थिरता परिणाम, Bermond-Thomassen अनुमान, Caccetta-Häggkvist अनुमान आदि

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

  1. H. Li प्रमेय का सामान्यीकरण: H. Li (2013) ने प्रमाणित किया कि न्यूनतम रंग-डिग्री शर्त δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2} इंद्रधनुष त्रिभुज के अस्तित्व की गारंटी देती है
  2. संरचित इंद्रधनुष त्रिभुज: स्वाभाविक रूप से कई इंद्रधनुष त्रिभुजों के शीर्ष या किनारे साझा करने के मामले पर विचार करना
  3. शास्त्रीय ग्राफ़ सिद्धांत के साथ संबंध: शास्त्रीय बुक ग्राफ़ और मित्रता ग्राफ़ की अवधारणाओं को किनारे-रंगीन ग्राफ़ सेटिंग में सामान्यीकृत करना

मौजूदा विधियों की सीमाएं

इंद्रधनुष त्रिभुजों पर मौजूदा अनुसंधान मुख्य रूप से एकल त्रिभुज के अस्तित्व पर केंद्रित है, कई इंद्रधनुष त्रिभुजों की संरचित व्यवस्था (जैसे शीर्ष या किनारे साझा करना) पर अनुसंधान कम है।

मुख्य योगदान

  1. मुख्य प्रमेय 3: प्रमाणित करता है कि जब δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} और n≥3k−2n\geq 3k-2 हो, तो ग्राफ़ GG में kk इंद्रधनुष त्रिभुज होते हैं जो एक किनारे को साझा करते हैं (किनारे-रंगीन बुक ग्राफ़ BkB_k)
  2. मुख्य प्रमेय 4: प्रमाणित करता है कि जब δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} और n≥2k+9n\geq 2k+9 हो, तो ग्राफ़ GG में kk इंद्रधनुष त्रिभुज होते हैं जो एक शीर्ष को साझा करते हैं (किनारे-रंगीन मित्रता ग्राफ़ FkF_k)
  3. H. Li प्रमेय में सुधार: जब k=2k=2 हो, तो दोनों मुख्य परिणाम H. Li की मूल प्रमेय में सुधार करते हैं
  4. तकनीकी नवाचार: Czygrinow आदि की इंद्रधनुष चक्र तकनीक और नवीनतम गणना तकनीकों को जोड़ता है
  5. चरम विश्लेषण: परिणामों की कसाई का विश्लेषण और चरम निर्माण प्रदान करता है

विधि विवरण

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

इनपुट: किनारे-रंगीन ग्राफ़ G=(V,E)G=(V,E), जहां ∣V∣=n|V|=n, किनारे-रंगीन फ़ंक्शन C:E→{1,2,…,k}C:E\to \{1,2,\ldots,k\}आउटपुट: यह निर्धारित करना कि क्या GG में kk इंद्रधनुष त्रिभुज एक किनारे को साझा करते हैं (या एक शीर्ष) बाधा शर्तें: न्यूनतम रंग-डिग्री δc(G)\delta^c(G) विशिष्ट सीमा को संतुष्ट करती है

मुख्य अवधारणाएं और तकनीकें

1. रंग-डिग्री संबंधित परिभाषाएं

  • रंग-डिग्री: dc(v)=∣{C(uv):u∈N(v)}∣d^c(v) = |\{C(uv) : u \in N(v)\}|
  • α\alpha-पड़ोस: Nα(v)={u∈N(v):C(uv)=α}N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}
  • एकवर्णी डिग्री: dmon(v)=max⁡{∣Nα(v)∣:α∈C(G)}d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}

2. प्रतिबंधित रंग तकनीक

Czygrinow आदि की "प्रतिबंधित रंग" अवधारणा को प्रस्तुत करता है:

  • शीर्ष vv और X⊆N(v)X \subseteq N(v) के लिए, यदि α=C(xy)\alpha = C(xy) ऐसा है कि vxyvxy एक इंद्रधनुष P3P_3 बनाता है और α∉C(y,N(y)∖X)\alpha \notin C(y, N(y)\setminus X), तो (v,X)(v,X) को yy के लिए रंग α\alpha प्रतिबंधित करना कहा जाता है
  • σv,X(y)\sigma_{v,X}(y) को (v,X)(v,X) द्वारा प्रतिबंधित रंगों की संख्या के रूप में दर्शाया जाता है

3. इंद्रधनुष त्रिभुज गणना

  • rt(v)rt(v): शीर्ष vv युक्त इंद्रधनुष त्रिभुजों की संख्या
  • rt(v,x)rt(v,x): शीर्ष vv और xx दोनों युक्त इंद्रधनुष त्रिभुजों की संख्या
  • rt(v,X)=∑x∈Xrt(v,x)rt(v,X) = \sum_{x \in X} rt(v,x)

मुख्य लेम्मा

लेम्मा 7 (गणना लेम्मा)

किनारे न्यूनतम ग्राफ़ GG और शीर्ष vv के लिए: rt(v,Ni(v))≥∑x∈Ni(v)(dc(x)+dc(v)−n)+di(v)∑1≤j≤s(dj(v)−1)−di(v)(di(v)−1)−∑y∈N!(v)dvyc(y,Ni(v))rt(v,N_i(v)) \geq \sum_{x\in N_i(v)}(d^c(x) + d^c(v) - n) + d_i(v)\sum_{1\leq j\leq s}(d_j(v)-1) - d_i(v)(d_i(v)-1) - \sum_{y\in N^!(v)}d^c_{vy}(y,N_i(v))

जहां N!(v)=⋃α∈C(G){Nα(v):∣Nα(v)∣=1}N^!(v) = \bigcup_{\alpha\in C(G)}\{N_\alpha(v) : |N_\alpha(v)| = 1\}।

लेम्मा 9 (एकवर्णी डिग्री विश्लेषण)

अधिकतम एकवर्णी डिग्री वाले शीर्ष vv के लिए, B(v)≥0B(v) \geq 0 है, और जब B(v)=0B(v) = 0 हो तो विशेष संरचनात्मक गुण मौजूद हैं।

प्रमाण रणनीति

प्रमेय 3 के प्रमाण का विचार

  1. मान लें कि kk साझा किनारे वाले इंद्रधनुष त्रिभुज मौजूद नहीं हैं
  2. अधिकतम एकवर्णी डिग्री वाले शीर्ष vv को चुनें
  3. लेम्मा 7 की गणना असमानता का उपयोग करें
  4. विरोधाभास के माध्यम से संतोषजनक संरचना के अस्तित्व को प्रमाणित करें

प्रमेय 4 के प्रमाण का विचार

  1. मिलान संख्या पर Erdős-Gallai की Turán संख्या सिद्धांत का उपयोग करें
  2. सहायक ग्राफ़ G△(v)G^\triangle(v) का निर्माण करें (vv युक्त इंद्रधनुष त्रिभुजों के किनारों से बना)
  3. G△(v)G^\triangle(v) की कवरिंग संख्या और मिलान संख्या का विश्लेषण करें
  4. सूक्ष्म डिग्री विश्लेषण के माध्यम से विरोधाभास प्राप्त करें

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

चरम निर्माण

उदाहरण 1: संतुलित पूर्ण 3-भाग ग्राफ़ G[V1,V2,V3]G[V_1,V_2,V_3] का निर्माण करें, जहां ∣V(G)∣=3k−3|V(G)|=3k-3, ∣V1∣=∣V2∣=∣V3∣=k−1|V_1|=|V_2|=|V_3|=k-1, सही रंगीन का उपयोग करते हुए। यह ग्राफ़ dc(v)=n+k−12d^c(v) = \frac{n+k-1}{2} को संतुष्ट करता है लेकिन BkB_k या FkF_k नहीं रखता है, जो प्रमेय 3 में शर्त "n≥3k−2n \geq 3k-2" की कसाई को प्रमाणित करता है।

तुलनात्मक विश्लेषण

पेपर परिणामों की निम्नलिखित शास्त्रीय परिणामों के साथ तुलना करता है:

  • H. Li प्रमेय: δc(G)≥n+12\delta^c(G) \geq \frac{n+1}{2} इंद्रधनुष त्रिभुज की गारंटी देता है
  • Erdős आदि के परिणाम: बुक ग्राफ़ और मित्रता ग्राफ़ की शास्त्रीय Turán संख्याएं
  • अरंगीन ग्राफ़ मामला: संबंधित न्यूनतम डिग्री शर्तें

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

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

संरचनाइस पेपर की शर्तशीर्ष संख्या आवश्यकताH. Li शर्तसुधार
B2B_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥4n \geq 4δc≥n+12\delta^c \geq \frac{n+1}{2}निर्माणात्मक सुधार
F2F_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥13n \geq 13δc≥n+12\delta^c \geq \frac{n+1}{2}निर्माणात्मक सुधार
BkB_kδc≥n+k−12\delta^c \geq \frac{n+k-1}{2}n≥3k−2n \geq 3k-2-नया परिणाम
FkF_kδc≥n+2k−32\delta^c \geq \frac{n+2k-3}{2}n≥2k+9n \geq 2k+9-नया परिणाम

कसाई विश्लेषण

  • प्रमेय 3 की कसाई: उदाहरण 1 दर्शाता है कि जब n≤3k−3n \leq 3k-3 हो तो मजबूत रंग-डिग्री शर्त δc≥n+k2\delta^c \geq \frac{n+k}{2} की आवश्यकता है
  • स्पर्शोन्मुख कसाई: जब k=o(n)k = o(n) हो तो परिणाम स्पर्शोन्मुख रूप से कसे हुए हैं

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

इंद्रधनुष त्रिभुज अनुसंधान

  1. H. Li (2013): पहली बार रंग-डिग्री शर्त δc≥n+12\delta^c \geq \frac{n+1}{2} इंद्रधनुष त्रिभुज की गारंटी देने के लिए प्रमाणित किया
  2. B. Li आदि (2014): प्रमाणित किया कि कमजोर शर्त ∑vdc(v)≥n(n+1)2\sum_{v} d^c(v) \geq \frac{n(n+1)}{2} भी पर्याप्त है
  3. X. Li आदि (2022): इंद्रधनुष त्रिभुजों का गणना संस्करण दिया

शास्त्रीय ग्राफ़ सिद्धांत परिणाम

  1. Mantel (1907): त्रिभुज-मुक्त ग्राफ़ के किनारों की संख्या की ऊपरी सीमा
  2. Erdős-Edwards-Khadžiivanov-Nikiforov: बुक ग्राफ़ की Turán संख्या
  3. Erdős आदि (1995): मित्रता ग्राफ़ की Turán संख्या

तकनीकी विधियां

  1. Czygrinow आदि (2021): इंद्रधनुष चक्रों के लिए प्रतिबंधित रंग तकनीक
  2. Erdős-Gallai (1959): मिलान संख्या की Turán सिद्धांत

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

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

  1. H. Li के इंद्रधनुष त्रिभुजों पर शास्त्रीय परिणाम को कई त्रिभुजों की साझा संरचना के मामले में सफलतापूर्वक सामान्यीकृत किया
  2. किनारे-रंगीन ग्राफ़ में बुक ग्राफ़ और मित्रता ग्राफ़ के अस्तित्व के लिए पर्याप्त शर्तें स्थापित कीं
  3. परिणामों की कसाई विश्लेषण और चरम निर्माण प्रदान किए

सीमाएं

  1. शीर्ष संख्या आवश्यकता: प्रमेय 4 को n≥2k+9n \geq 2k+9 की शर्त अपेक्षाकृत मजबूत है
  2. तकनीकी जटिलता: प्रमाण कई जटिल गणना तकनीकों और संरचनात्मक विश्लेषण को शामिल करते हैं
  3. सामान्यीकरण की डिग्री: परिणाम मुख्य रूप से विशिष्ट साझा पैटर्न (एकल किनारा या एकल शीर्ष) के लिए हैं

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

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

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

लाभ

  1. सैद्धांतिक योगदान महत्वपूर्ण है: महत्वपूर्ण शास्त्रीय परिणामों को सफलतापूर्वक सामान्यीकृत किया, नई सैद्धांतिक ढांचा स्थापित किया
  2. तकनीकी नवाचार: कई आधुनिक तकनीकों (प्रतिबंधित रंग, गणना विधि, Turán सिद्धांत) को कुशलतापूर्वक जोड़ा
  3. परिणाम पूर्णता: न केवल अस्तित्व परिणाम देता है, बल्कि कसाई और चरम मामलों का विश्लेषण भी करता है
  4. लेखन स्पष्टता: पेपर संरचना तार्किक है, प्रमाण विचार स्पष्ट हैं

कमियां

  1. प्रमाण जटिलता अधिक है: तकनीकी विवरण अधिक हैं, परिणामों की पहुंच को प्रभावित कर सकते हैं
  2. अनुप्रयोग सीमा: मुख्य रूप से सैद्धांतिक परिणाम हैं, व्यावहारिक अनुप्रयोग परिदृश्य पर्याप्त स्पष्ट नहीं हैं
  3. स्थिरांक कारक: कुछ शर्तों में स्थिरांक (जैसे 2k+92k+9) इष्टतम नहीं हो सकते हैं

प्रभाव

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

लागू परिदृश्य

यह अनुसंधान मुख्य रूप से निम्नलिखित के लिए लागू है:

  1. चरम संयोजन विज्ञान सैद्धांतिक अनुसंधान
  2. ग्राफ़ रंगीन सिद्धांत
  3. संरचनात्मक ग्राफ़ सिद्धांत में अस्तित्व समस्याएं
  4. संयोजन अनुकूलन में उप-संरचना पहचान समस्याएं

संदर्भ

पेपर 29 महत्वपूर्ण संदर्भों को उद्धृत करता है, जिनमें शामिल हैं:

  • H. Li (2013): Rainbow C3C_3's and C4C_4's in edge-colored graphs
  • Erdős, Füredi, Gould, Gunderson (1995): Extremal graphs for intersecting triangles
  • Czygrinow, Molla, Nagle, Oursler (2021): On odd rainbow cycles in edge-colored graphs
  • संयोजन गणित और ग्राफ़ सिद्धांत क्षेत्र के कई अन्य शास्त्रीय साहित्य