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)$ を、 $n$ 個の頂点を持つ $r$ -一様超グラフにおいて、 $k$ 本の辺を含まず、かつこれらの辺が最大 $s$ 個の頂点をカバーする最大辺数とする。Brown、Erdős、Sósは1973年に、すべての $k$ に対して極限 $\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)$ が存在することを予想した。最近、DelcourtとPostleがこの予想を解決し、Shangguanがすべての一様性 $r\ge 4$ に推広した。本論文は $k=8$ の場合を考察し、各 $r\ge 4$ に対する極限値を決定し、 $r=3$ の場合の下界を与える。

研究背景と動機

核心問題: Brown-Erdős-Sós問題は $r$ -一様超グラフのTurán数を研究する。すなわち、特定の禁止部分グラフを避ける条件下で、 $n$ 個の頂点を持つ超グラフが含むことができる最大辺数である。
問題の重要性: これは極値組合論の基本的な問題の一つであり、Ramsey理論、Turán理論などの中核領域と密接に関連している。この問題の解決は超グラフの構造的性質を理解する上で重要な意義を持つ。
既存の進展:
- Brown、Erdős、Sósは $f^{(r)}(n;s,k) = \Theta(n^t)$ を証明した。ここで $t = (rk-s)/(k-1)$
- $t=2$ の場合（すなわち $s = rk-2k+2$ ）、極限 $\pi(r,k) := \lim_{n\to\infty} n^{-2}f^{(r)}(n;rk-2k+2,k)$ の存在性が証明されている
- $k \in \{2,3,4,5,6,7\}$ に対して、極限値が既知である
研究動機: $k=8$ は次の自然な研究対象であり、この場合は新たな複雑性を示す。特に $r=3$ と $r\ge 4$ の場合で異なる挙動を示す。

核心的貢献

主定理: すべての $r \geq 4$ に対して、 $\pi(r,8) = \frac{1}{r^2-r}$ を決定した
下界結果: $\pi(3,8) \geq \frac{3}{16}$ を証明し、この下界が最適であることを予想した
構成方法: 下界を達成する明示的な構成を提供した。射影平面の接続グラフに基づく
構造分析: $G^{(r)}_8$ -自由超グラフの構造を深く分析した。特に2-クラスタの分類
応用: 一般化Ramsey数との関連を確立し、 $\lim_{n\to\infty} \frac{GR(n,18,146)}{n^2} = \frac{5}{12}$ を得た

方法の詳細

問題の定義

$k=8$ の場合、関数 $f^{(r)}(n; rk-2k+2, k)$ の漸近挙動を研究する。すなわち、極限 $\pi(r,8) = \lim_{n\to\infty} n^{-2}f^{(r)}(n; 8r-14, 8)$ の値を決定する。

下界構成方法

基本構成単位

R-グラフ: 5頂点3辺の3-グラフ $R$ を定義する。1本の辺 $abc$ と1つのダイヤモンド $\{buv, cuv\}$ から構成される
パス族: Desarguesian射影平面を利用して2-パス族 $P$ を構成する。特定の疎性と連結性条件を満たす

確率削除方法

射影平面の接続グラフから開始し、二部グラフ $G'$ を構成する
確率 $(log m)/m^{1/2}$ で2-パスをランダムに選択する
確率削除方法を使用して密集配置を形成するパスを削除する
各2-パス上に $R$ -グラフの副本を配置する

主要補題

補題3.2: 十分に大きい素数べき $q$ に対して、2-パス族 $P$ が存在し、以下を満たす：

$|P| = \Omega(m^{3/2} \log m)$
並集合 $\bigcup_{P\in P} P$ は $O(m^{3/2})$ 本の辺を持つ
並集合は三角形、4-圏、5-圏を含まない
任意の $i \in [8]$ に対して、各 $i$ -部分集合の頂点数は少なくとも $i+2$ である

上界証明方法

マージ戦略

1-マージ: 辺集合を連結な1-クラスタ（実際には木）に分割する
2-マージ: さらにマージして2-クラスタを得る。 $\{1\}|\{2\}$ -マージ可能条件を通じて

構造分析

補題4.7: $|F| \geq 9$ の任意の2-クラスタ $F$ に対して、 $F$ は以下の族の一つに属する：

$A$ : 組み合わせが $(5,2,2)$ の9辺2-クラスタ
$B$ : 組み合わせが $(1,2,4,2)$ の9辺2-クラスタ
$C_1, C_2$ : 異なる組み合わせの2-クラスタ
$E, F$ : 特殊構造の2-クラスタ
$S_i$ : 1本の1-木と $i$ 個のダイヤモンドから構成される $(2i+1)$ 辺2-クラスタ

重み付け割り当て

$r \geq 5$ と $r = 4$ に対して異なる重み関数を採用する：

$r \geq 5$ の場合: $w_F(uv) = \begin{cases} 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}$