2025-11-25T13:16:17.951447

On the quadratic 8-edge case of the Brown-Erdős-Sós problem

Pikhurko, Sun
Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ edges on at most $s$ vertices. Brown, Erdős and Sós conjectured in 1973 that the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)$ exists for all $k$. Recently, Delcourt and Postle settled the conjecture and their approach was generalised by Shangguan to every uniformity $r\ge 4$: the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(r)}(n;rk-2k+2,k)$ exists for all $r\ge 3$ and $k\ge 2$. The value of the limit is currently known for $k\in \{2,3,4,5,6,7\}$ due to various results authored by Glock, Joos, Kim, Kühn, Lichev, Pikhurko, Rödl and Sun. In this paper we consider the case $k=8$, determining the value of the limit for each $r\ge 4$ and presenting a lower bound for $k=3$ that we conjecture to be sharp.
academic

Brown-Erdős-Sós समस्या के द्विघात 8-किनारे मामले पर

मूल जानकारी

  • पेपर ID: 2506.01739
  • शीर्षक: Brown-Erdős-Sós समस्या के द्विघात 8-किनारे मामले पर
  • लेखक: Oleg Pikhurko, Shumin Sun (University of Warwick)
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 25 अक्टूबर, 2016 (arXiv संस्करण 2)
  • पेपर लिंक: https://arxiv.org/abs/2506.01739

सारांश

यह पेपर Brown-Erdős-Sós समस्या के द्विघात 8-किनारे मामले का अध्ययन करता है। मान लीजिए f(r)(n;s,k)f^{(r)}(n;s,k) को nn शीर्षों के rr-समान अतिग्राफ में kk किनारों की अधिकतम संख्या के रूप में परिभाषित किया जाता है जो ss शीर्षों को कवर करते हैं। Brown, Erdős और Sós ने 1973 में अनुमान लगाया कि सभी kk के लिए, सीमा lim⁡n→∞n−2f(3)(n;k+2,k)\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k) मौजूद है। हाल ही में Delcourt और Postle ने इस अनुमान को हल किया, और Shangguan ने इसे सभी समानता r≥4r\ge 4 तक सामान्यीकृत किया। यह पेपर k=8k=8 के मामले पर विचार करता है, प्रत्येक r≥4r\ge 4 के लिए सीमा का मान निर्धारित करता है, और r=3r=3 के लिए निचली सीमा प्रदान करता है।

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

  1. मूल समस्या: Brown-Erdős-Sós समस्या rr-समान अतिग्राफ की Turán संख्या का अध्ययन करती है, अर्थात् निषिद्ध उप-ग्राफ से बचते हुए nn शीर्षों के अतिग्राफ में अधिकतम किनारों की संख्या।
  2. समस्या की महत्ता: यह चरम संयोजन गणित की मौलिक समस्याओं में से एक है, जो Ramsey सिद्धांत, Turán सिद्धांत आदि मूल क्षेत्रों से निकटता से संबंधित है। इस समस्या का समाधान अतिग्राफ के संरचनात्मक गुणों को समझने के लिए महत्वपूर्ण है।
  3. मौजूदा प्रगति:
    • Brown, Erdős और Sós ने सिद्ध किया कि f(r)(n;s,k)=Θ(nt)f^{(r)}(n;s,k) = \Theta(n^t), जहाँ t=(rk−s)/(k−1)t = (rk-s)/(k-1)
    • जब t=2t=2 हो (अर्थात् s=rk−2k+2s = rk-2k+2), सीमा π(r,k):=lim⁡n→∞n−2f(r)(n;rk−2k+2,k)\pi(r,k) := \lim_{n\to\infty} n^{-2}f^{(r)}(n;rk-2k+2,k) का अस्तित्व सिद्ध हो चुका है
    • k∈{2,3,4,5,6,7}k \in \{2,3,4,5,6,7\} के लिए, सीमा मान ज्ञात हैं
  4. अनुसंधान प्रेरणा: k=8k=8 अगला प्राकृतिक अनुसंधान लक्ष्य है, और यह मामला नई जटिलता प्रदर्शित करता है, विशेषकर जब r=3r=3 और r≥4r\ge 4 में व्यवहार भिन्न हो।

मुख्य योगदान

  1. मुख्य प्रमेय: सभी r≥4r \geq 4 के लिए, π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r} निर्धारित किया गया है
  2. निचली सीमा परिणाम: π(3,8)≥316\pi(3,8) \geq \frac{3}{16} सिद्ध किया गया है, और यह अनुमान लगाया जाता है कि यह निचली सीमा तंग है
  3. निर्माण विधि: निचली सीमा को प्राप्त करने वाली स्पष्ट निर्माण प्रदान की गई है, जो प्रक्षेपी तल के आपतन ग्राफ पर आधारित है
  4. संरचना विश्लेषण: G8(r)G^{(r)}_8-मुक्त अतिग्राफ की संरचना का गहन विश्लेषण, विशेषकर 2-क्लस्टर का वर्गीकरण
  5. अनुप्रयोग: सामान्यीकृत Ramsey संख्याओं के साथ संबंध स्थापित किया गया है, lim⁡n→∞GR(n,18,146)n2=512\lim_{n\to\infty} \frac{GR(n,18,146)}{n^2} = \frac{5}{12} प्राप्त किया गया है

विधि विवरण

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

फलन f(r)(n;rk−2k+2,k)f^{(r)}(n; rk-2k+2, k) के स्पर्शोन्मुख व्यवहार का अध्ययन करें जब k=8k=8 हो, अर्थात् सीमा π(r,8)=lim⁡n→∞n−2f(r)(n;8r−14,8)\pi(r,8) = \lim_{n\to\infty} n^{-2}f^{(r)}(n; 8r-14, 8) का मान निर्धारित करें।

निचली सीमा निर्माण विधि

मूल निर्माण इकाई

  • R-ग्राफ: 5 शीर्षों और 3 किनारों का 3-ग्राफ RR परिभाषित किया गया है, जिसमें एक किनारा abcabc और एक हीरा {buv,cuv}\{buv, cuv\} शामिल है
  • पथ परिवार: Desarguesian प्रक्षेपी तल का उपयोग करके 2-पथ परिवार PP का निर्माण किया गया है, जो विशिष्ट विरलता और संयोजकता शर्तों को संतुष्ट करता है

संभाव्य विलोपन विधि

  1. प्रक्षेपी तल के आपतन ग्राफ से शुरू करके, द्विपक्षीय ग्राफ G′G' का निर्माण करें
  2. संभावना (logm)/m1/2(log m)/m^{1/2} के साथ 2-पथ को यादृच्छिक रूप से चुनें
  3. घने विन्यास बनाने वाले पथों को हटाने के लिए संभाव्य विलोपन विधि का उपयोग करें
  4. प्रत्येक 2-पथ पर RR-ग्राफ की प्रतियाँ रखें

मुख्य लेम्मा

लेम्मा 3.2: पर्याप्त बड़े अभाज्य शक्ति qq के लिए, 2-पथ परिवार PP मौजूद है जो संतुष्ट करता है:

  • ∣P∣=Ω(m3/2log⁡m)|P| = \Omega(m^{3/2} \log m)
  • संघ ग्राफ ⋃P∈PP\bigcup_{P\in P} P में O(m3/2)O(m^{3/2}) किनारे हैं
  • संघ ग्राफ त्रिभुज-मुक्त, 4-चक्र-मुक्त और 5-चक्र-मुक्त है
  • किसी भी i∈[8]i \in [8] के लिए, प्रत्येक ii-उपसमुच्चय के शीर्षों की संख्या कम से कम i+2i+2 है

ऊपरी सीमा प्रमाण विधि

विलय रणनीति

  1. 1-विलय: किनारों के समुच्चय को जुड़े हुए 1-क्लस्टर (वास्तव में वृक्ष) में विभाजित करें
  2. 2-विलय: {1}∣{2}\{1\}|\{2\}-विलय योग्य शर्त के माध्यम से 2-क्लस्टर प्राप्त करने के लिए आगे विलय करें

संरचना विश्लेषण

लेम्मा 4.7: किसी भी ∣F∣≥9|F| \geq 9 के 2-क्लस्टर FF के लिए, FF निम्नलिखित परिवारों में से एक है:

  • AA: (5,2,2)(5,2,2) संयोजन के साथ 9-किनारे 2-क्लस्टर
  • BB: (1,2,4,2)(1,2,4,2) संयोजन के साथ 9-किनारे 2-क्लस्टर
  • C1,C2C_1, C_2: विभिन्न संयोजन के 2-क्लस्टर
  • E,FE, F: विशेष संरचना के 2-क्लस्टर
  • SiS_i: 1 एक 1-वृक्ष और ii हीरों से बने (2i+1)(2i+1)-किनारे 2-क्लस्टर

भार आवंटन

r≥5r \geq 5 और r=4r = 4 के लिए विभिन्न भार फलन का उपयोग किया जाता है:

r≥5r \geq 5 के लिए:

1 & \text{यदि } 1 \in C_F(uv) \\ 1/3 & \text{यदि } 2 \in C_F(uv) \text{ और } 1 \notin C_F(uv) \\ 0 & \text{अन्यथा} \end{cases}$$ **$r = 4$ के लिए**: 5 सहायक फलनों $h_i^F$ के अधिकतम मान को भार के रूप में उपयोग करें। ## प्रायोगिक सेटअप यह पेपर शुद्ध सैद्धांतिक अनुसंधान है, जिसमें कोई कम्प्यूटेशनल प्रयोग नहीं है। सभी परिणाम कठोर गणितीय प्रमाण के माध्यम से प्राप्त किए गए हैं। ### प्रमाण सत्यापन - निचली सीमा स्पष्ट निर्माण द्वारा सत्यापित की गई है - ऊपरी सीमा विस्तृत केस विश्लेषण और भार आवंटन विधि द्वारा सिद्ध की गई है - सभी मुख्य लेम्मा में पूर्ण गणितीय प्रमाण हैं ## प्रायोगिक परिणाम ### मुख्य परिणाम **प्रमेय 1.1**: प्रत्येक $r \geq 4$ के लिए, $\pi(r,8) = \frac{1}{r^2-r}$। **प्रमेय 1.2**: $\pi(3,8) \geq \frac{3}{16}$। **अनुमान 1.3**: $\pi(3,8) = \frac{3}{16}$। ### ज्ञात परिणामों के साथ तुलना - $\pi(r,2) = \frac{1}{r^2-r}$ (Rödl) - $\pi(r,4) = \frac{1}{r^2-r}$ (Glock आदि) - $\pi(r,6) = \frac{1}{r^2-r}$ $r \geq 4$ के लिए (Glock आदि) - $\pi(3,6) = \frac{61}{330}$ (विशेष मामला) ### नई खोजें 1. **दहलीज घटना**: $r=4$ वह न्यूनतम समानता है जिसके लिए $\pi(r,8) = \frac{1}{r^2-r}$ सत्य है 2. **संरचना जटिलता**: $k=8$ का मामला पहले अध्ययन किए गए $k$ मानों की तुलना में अधिक जटिल 2-क्लस्टर संरचना प्रदर्शित करता है 3. **Ramsey संबंध**: सामान्यीकृत Ramsey संख्याओं के साथ नए संबंध स्थापित किए गए हैं ## संबंधित कार्य ### ऐतिहासिक विकास 1. **Brown-Erdős-Sós (1973)**: मूल अनुमान और मूल सीमा प्रस्तावित की गई 2. **Rödl (1985)**: $k=2$ के मामले को हल किया 3. **Glock (2019)**: $k=3$ के मामले को हल किया 4. **Delcourt-Postle (2024)**: सीमा के अस्तित्व को सिद्ध किया 5. **Shangguan (2023)**: सभी समानताओं तक सामान्यीकृत किया ### तकनीकी विकास - **संघर्ष-मुक्त मिलान सिद्धांत**: Delcourt-Postle और Glock आदि द्वारा विकसित मुख्य तकनीक - **भार आवंटन विधि**: Glock आदि के कार्य के आधार पर विकसित ऊपरी सीमा तकनीक - **संभाव्य निर्माण**: बीजगणितीय ज्यामिति संरचनाओं पर आधारित संभाव्य विधि ## निष्कर्ष और चर्चा ### मुख्य निष्कर्ष 1. $r \geq 4$ के लिए $\pi(r,8)$ का मान पूरी तरह से निर्धारित किया गया है 2. $r=3$ के मामले के लिए संभवतः इष्टतम सीमा प्रदान की गई है 3. सामान्यीकृत Ramsey संख्याओं के साथ नए संबंध स्थापित किए गए हैं ### सीमाएँ 1. **$r=3$ का मामला**: केवल निचली सीमा प्राप्त की गई है, ऊपरी सीमा मिलान अभी भी खुली समस्या है 2. **निर्माण जटिलता**: निचली सीमा निर्माण काफी तकनीकी है, संभवतः सरल निर्माण मौजूद हो सकता है 3. **सामान्यीकरण**: विधि की बड़े $k$ मानों के लिए प्रयोज्यता अस्पष्ट है ### भविष्य की दिशाएँ 1. $\pi(3,8) = \frac{3}{16}$ के अनुमान को सिद्ध करें 2. $k \geq 9$ के मामलों का अध्ययन करें 3. अधिक सामान्य निर्माण और ऊपरी सीमा तकनीकें खोजें 4. अन्य चरम समस्याओं के साथ संबंधों की खोज करें ## गहन मूल्यांकन ### शक्तियाँ 1. **तकनीकी नवाचार**: नई 2-क्लस्टर वर्गीकरण और भार आवंटन तकनीकें विकसित की गई हैं 2. **निर्माण की कुशलता**: प्रक्षेपी तल पर आधारित निर्माण गहन ज्यामितीय अंतर्दृष्टि प्रदर्शित करता है 3. **पूर्णता**: $r \geq 4$ के लिए पूर्ण समाधान प्रदान किया गया है 4. **लेखन स्पष्टता**: तकनीकी विवरण अच्छी तरह से संगठित हैं, समझने में आसान हैं ### कमियाँ 1. **$r=3$ अधूरा**: मुख्य खुली समस्या अभी भी अनसुलझी है 2. **विधि की विशेषता**: तकनीक $k=8$ के लिए अत्यधिक लक्षित है, सामान्यीकरण क्षमता सीमित है 3. **कम्प्यूटेशनल जटिलता**: कुछ प्रमाण प्रक्रियाएँ काफी लंबी और तकनीकी हैं ### प्रभाव 1. **सैद्धांतिक योगदान**: Brown-Erdős-Sós समस्या के अनुसंधान को आगे बढ़ाता है 2. **पद्धति विज्ञान**: समान समस्याओं के लिए नई तकनीकी उपकरण प्रदान करता है 3. **अनुप्रयोग मूल्य**: Ramsey सिद्धांत के साथ संबंध नई अनुसंधान दिशाएँ खोलता है ### प्रयोज्य परिदृश्य यह विधि निम्नलिखित के लिए उपयुक्त है: 1. अतिग्राफ चरम समस्याओं का अनुसंधान 2. निषिद्ध उप-ग्राफ की Turán-प्रकार की समस्याएँ 3. संयोजन अनुकूलन में संरचना विश्लेषण 4. बीजगणितीय संयोजन गणित के अनुप्रयोग ## संदर्भ पेपर इस क्षेत्र के मूल साहित्य का हवाला देता है, जिसमें शामिल हैं: - Brown, Erdős, Sós का मूल कार्य - Delcourt-Postle का सफलता प्राप्त परिणाम - Glock आदि का श्रृंखला कार्य - Shangguan का सामान्यीकृत परिणाम - Bennett आदि द्वारा सामान्यीकृत Ramsey संख्याओं पर कार्य --- **समग्र मूल्यांकन**: यह संयोजन गणित में एक उच्च गुणवत्ता वाला सैद्धांतिक पेपर है, जो Brown-Erdős-Sós समस्या के अनुसंधान में महत्वपूर्ण प्रगति प्राप्त करता है। यद्यपि मुख्य खुली समस्या ($r=3$ का मामला) अभी भी पूरी तरह से अनसुलझी है, पेपर के तकनीकी योगदान और विधि नवाचार इस क्षेत्र के बाद के अनुसंधान के लिए एक मजबूत आधार स्थापित करते हैं।