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

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

Basic Information

  • Paper ID: 2506.01739
  • Title: On the quadratic 8-edge case of the Brown-Erdős-Sós problem
  • Authors: Oleg Pikhurko, Shumin Sun (University of Warwick)
  • Classification: math.CO (Combinatorics)
  • Publication Date: October 16, 2025 (arXiv version 2)
  • Paper Link: https://arxiv.org/abs/2506.01739

Abstract

This paper investigates the quadratic 8-edge case of the Brown-Erdős-Sós problem. Let f(r)(n;s,k)f^{(r)}(n;s,k) denote the maximum number of edges in an rr-uniform hypergraph on nn vertices that does not contain kk edges covering at most ss vertices. Brown, Erdős, and Sós conjectured in 1973 that for all kk, the limit lim⁡n→∞n−2f(3)(n;k+2,k)\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k) exists. This conjecture was recently resolved by Delcourt and Postle, and generalized to all uniformities r≥4r\ge 4 by Shangguan. This paper addresses the case k=8k=8, determining the value of the limit for each r≥4r\ge 4 and providing a lower bound for r=3r=3.

Research Background and Motivation

  1. Core Problem: The Brown-Erdős-Sós problem studies Turán numbers for rr-uniform hypergraphs, namely the maximum number of edges in an nn-vertex hypergraph while avoiding specific forbidden subgraphs.
  2. Problem Significance: This is a fundamental problem in extremal combinatorics, closely related to core areas such as Ramsey theory and Turán theory. Resolving this problem is crucial for understanding the structural properties of hypergraphs.
  3. Existing Progress:
    • Brown, Erdős, and Sós proved that f(r)(n;s,k)=Θ(nt)f^{(r)}(n;s,k) = \Theta(n^t), where t=(rk−s)/(k−1)t = (rk-s)/(k-1)
    • When t=2t=2 (i.e., s=rk−2k+2s = rk-2k+2), the existence of the limit π(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) has been established
    • For k∈{2,3,4,5,6,7}k \in \{2,3,4,5,6,7\}, the limit values are known
  4. Research Motivation: The case k=8k=8 is the natural next target, exhibiting new complexities, particularly in the different behaviors for r=3r=3 versus r≥4r\ge 4.

Core Contributions

  1. Main Theorem: For all r≥4r \geq 4, π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r} is determined
  2. Lower Bound Result: Proves that π(3,8)≥316\pi(3,8) \geq \frac{3}{16}, with a conjecture that this bound is tight
  3. Construction Method: Provides explicit constructions achieving the lower bound, based on incidence graphs of projective planes
  4. Structural Analysis: Provides in-depth analysis of the structure of G8(r)G^{(r)}_8-free hypergraphs, particularly the classification of 2-clusters
  5. Applications: Establishes connections with generalized Ramsey numbers, obtaining lim⁡n→∞GR(n,18,146)n2=512\lim_{n\to\infty} \frac{GR(n,18,146)}{n^2} = \frac{5}{12}

Methodology Details

Problem Formulation

Study the asymptotic behavior of f(r)(n;rk−2k+2,k)f^{(r)}(n; rk-2k+2, k) when k=8k=8, namely determining the value of the limit π(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).

Lower Bound Construction Method

Basic Construction Units

  • RR-graphs: Define a 3-uniform hypergraph RR on 5 vertices with 3 edges, consisting of one edge abcabc and a diamond {buv,cuv}\{buv, cuv\}
  • Path Families: Utilize Desarguesian projective planes to construct 2-path families PP satisfying specific sparsity and connectivity conditions

Probabilistic Deletion Method

  1. Begin with the incidence graph of a projective plane, constructing a bipartite graph G′G'
  2. Randomly select 2-paths with probability (logm)/m1/2(log m)/m^{1/2}
  3. Use probabilistic deletion to remove paths forming dense configurations
  4. Place copies of RR-graphs on each 2-path

Key Lemma

Lemma 3.2: For sufficiently large prime powers qq, there exists a 2-path family PP satisfying:

  • ∣P∣=Ω(m3/2log⁡m)|P| = \Omega(m^{3/2} \log m)
  • The union ⋃P∈PP\bigcup_{P\in P} P has O(m3/2)O(m^{3/2}) edges
  • The union is triangle-free, 4-cycle-free, and 5-cycle-free
  • For any i∈[8]i \in [8], every ii-subset of vertices has at least i+2i+2 vertices

Upper Bound Proof Method

Merging Strategy

  1. 1-merging: Partition the edge set into connected 1-clusters (essentially trees)
  2. 2-merging: Further merge to obtain 2-clusters via {1}∣{2}\{1\}|\{2\}-mergeability conditions

Structural Analysis

Lemma 4.7: For any 2-cluster FF with ∣F∣≥9|F| \geq 9, FF belongs to one of the following families:

  • AA: 9-edge 2-cluster with composition (5,2,2)(5,2,2)
  • BB: 9-edge 2-cluster with composition (1,2,4,2)(1,2,4,2)
  • C1,C2C_1, C_2: 2-clusters with different compositions
  • E,FE, F: 2-clusters with special structures
  • SiS_i: (2i+1)(2i+1)-edge 2-cluster consisting of one 1-tree and ii diamonds

Weight Assignment

Different weight functions are used for r≥5r \geq 5 and r=4r = 4:

For r≥5r \geq 5:

1 & \text{if } 1 \in C_F(uv) \\ 1/3 & \text{if } 2 \in C_F(uv) \text{ and } 1 \notin C_F(uv) \\ 0 & \text{otherwise} \end{cases}$$ **For $r = 4$**: The maximum of five auxiliary functions $h_i^F$ is used as the weight. ## Experimental Setup This is a pure theoretical research paper with no computational experiments. All results are obtained through rigorous mathematical proofs. ### Proof Verification - Lower bounds are verified through explicit constructions - Upper bounds are proved through exhaustive case analysis and weight assignment methods - All key lemmas have complete mathematical proofs ## Experimental Results ### Main Results **Theorem 1.1**: For each $r \geq 4$, $\pi(r,8) = \frac{1}{r^2-r}$. **Theorem 1.2**: $\pi(3,8) \geq \frac{3}{16}$. **Conjecture 1.3**: $\pi(3,8) = \frac{3}{16}$. ### Comparison with Known Results - $\pi(r,2) = \frac{1}{r^2-r}$ (Rödl) - $\pi(r,4) = \frac{1}{r^2-r}$ (Glock et al.) - $\pi(r,6) = \frac{1}{r^2-r}$ for $r \geq 4$ (Glock et al.) - $\pi(3,6) = \frac{61}{330}$ (special case) ### Novel Findings 1. **Threshold Phenomenon**: $r=4$ is the minimum uniformity for which $\pi(r,8) = \frac{1}{r^2-r}$ holds 2. **Structural Complexity**: The case $k=8$ exhibits more complex 2-cluster structures than previously studied values of $k$ 3. **Ramsey Connection**: Establishes new connections with generalized Ramsey numbers ## Related Work ### Historical Development 1. **Brown-Erdős-Sós (1973)**: Proposed the original conjecture and basic bounds 2. **Rödl (1985)**: Resolved the case $k=2$ 3. **Glock (2019)**: Resolved the case $k=3$ 4. **Delcourt-Postle (2024)**: Proved the existence of limits 5. **Shangguan (2023)**: Generalized to all uniformities ### Technical Development - **Conflict-free Matching Theory**: Key techniques developed by Delcourt-Postle and Glock et al. - **Weight Assignment Method**: Upper bound technique developed based on work by Glock et al. - **Probabilistic Construction**: Probabilistic methods based on algebraic geometric structures ## Conclusions and Discussion ### Main Conclusions 1. Completely determines the value of $\pi(r,8)$ for $r \geq 4$ 2. Provides possibly optimal bounds for the case $r=3$ 3. Establishes new connections with generalized Ramsey numbers ### Limitations 1. **Case $r=3$**: Only lower bounds obtained; matching upper bounds remain open 2. **Construction Complexity**: Lower bound construction is quite technical; simpler constructions may exist 3. **Generalization**: Applicability of the method to larger values of $k$ is unclear ### Future Directions 1. Prove the conjecture $\pi(3,8) = \frac{3}{16}$ 2. Investigate cases with $k \geq 9$ 3. Seek more general construction and upper bound techniques 4. Explore connections with other extremal problems ## In-Depth Evaluation ### Strengths 1. **Technical Innovation**: Develops new 2-cluster classification and weight assignment techniques 2. **Elegant Construction**: The construction based on projective planes demonstrates deep geometric insights 3. **Completeness**: Provides complete solution for $r \geq 4$ 4. **Clear Exposition**: Technical details are well-organized and easy to follow ### Weaknesses 1. **Incompleteness for $r=3$**: The main open problem remains unresolved 2. **Method Specificity**: Techniques are highly tailored to $k=8$ with limited generalizability 3. **Computational Complexity**: Some proofs are quite lengthy and technical ### Impact 1. **Theoretical Contribution**: Advances research on the Brown-Erdős-Sós problem 2. **Methodology**: Provides new technical tools for similar problems 3. **Application Value**: Connections with Ramsey theory open new research directions ### Applicable Scenarios The method is applicable to: 1. Research on extremal problems for hypergraphs 2. Turán-type problems with forbidden subgraphs 3. Structural analysis in combinatorial optimization 4. Applications of algebraic combinatorics ## References The paper cites core literature in the field, including: - Original work by Brown, Erdős, and Sós - Breakthrough results by Delcourt-Postle - Series of works by Glock et al. - Generalization results by Shangguan - Work on generalized Ramsey numbers by Bennett et al. --- **Overall Assessment**: This is a high-quality theoretical combinatorics paper that makes significant progress on the Brown-Erdős-Sós problem. While the main open problem (the case $r=3$) remains incompletely resolved, the paper's technical contributions and methodological innovations provide a solid foundation for subsequent research in this field.