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

基本信息

  • 论文ID: 2506.01739
  • 标题: On the quadratic 8-edge case of the Brown-Erdős-Sós problem
  • 作者: Oleg Pikhurko, Shumin Sun (University of Warwick)
  • 分类: math.CO (组合数学)
  • 发表时间: 2025年10月16日 (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-free超图的结构，特别是2-cluster的分类
  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. 随机选择2-路径，概率为(logm)/m1/2(log m)/m^{1/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-cluster（实际上是树）
  2. 2-合并: 进一步合并得到2-cluster，通过{1}∣{2}\{1\}|\{2\}-可合并条件

结构分析

引理4.7: 对于任何∣F∣≥9|F| \geq 9的2-cluster FF，FF属于以下族之一：

  • AA: 组合为(5,2,2)(5,2,2)的9边2-cluster
  • BB: 组合为(1,2,4,2)(1,2,4,2)的9边2-cluster
  • C1,C2C_1, C_2: 不同组合的2-cluster
  • E,FE, F: 特殊结构的2-cluster
  • SiS_i: 由1个1-树和ii个钻石组成的(2i+1)(2i+1)边2-cluster

权重分配

对于r≥5r \geq 5和r=4r = 4采用不同的权重函数：

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}$$ **$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}$ for $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-cluster结构 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-cluster分类和权重分配技术 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$的情况）仍未完全解决，但论文的技术贡献和方法创新为该领域的后续研究奠定了坚实基础。