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
  • タイトル: On the quadratic 8-edge case of the Brown-Erdős-Sós problem
  • 著者: Oleg Pikhurko、Shumin Sun（ウォーリック大学）
  • 分類: 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-自由超グラフの構造を深く分析した。特に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}を得た

方法の詳細

問題の定義

k=8k=8の場合、関数f(r)(n;rk−2k+2,k)f^{(r)}(n; rk-2k+2, k)の漸近挙動を研究する。すなわち、極限π(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を定義する。1本の辺abcabcと1つのダイヤモンド{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-マージ: さらにマージして2-クラスタを得る。{1}∣{2}\{1\}|\{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{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-クラスタ構造を示す 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$の場合）はまだ完全には解決されていないが、論文の技術的貢献と方法的革新は、本分野の後続研究のための堅実な基礎を築いている。