On the $(k+2,k)$-problem of Brown, Erd\H{o}s and Sós for even integers $k$

この論文は、ブラウン・エルデシュ・ソスによる$(k+2,k)$-問題において、$k$が偶数で $r \geq 2+\sqrt{\frac{3}{2}k-4}$ となるすべての場合について、極限値 $\lim_{n\to\infty} n^{-2} f^{(r)}(n;rk-2k+2,k)$ が $\frac{1}{r^2-r}$ であることを証明したものである。

要約

この論文は、数学の中でも「組み合わせ論（どう物事を組み合わせるか）」という分野の、非常に難解なパズルを解いたというニュースです。

専門用語をすべて捨てて、**「巨大なレゴブロックの城」**という物語に例えて説明しましょう。

1. 物語の舞台：レゴの城と「禁止された形」

想像してください。
あなたには無数のレゴブロック（頂点）と、それらを繋ぐ特別な「連結部品（辺）」があります。
この連結部品は、2 つのブロックだけでなく、**「r 個のブロック」**を一度に繋ぐことができます（これを「r-グラフ」と呼びます）。

さて、ここに**「禁止された形」というルールがあります。
「もし、k 個の連結部品を全部集めると、s 個以下のブロックしか使っていないような小さな城ができちゃったら、それはNG**！」というルールです。

このルールを守りながら、**「n 個のブロック」を使って、「できるだけ多くの連結部品（辺）」**を繋げるにはどうすればいいでしょうか？
これがこの論文が取り組んでいる「ブラウン・エルドス・ソス問題」というパズルです。

2. 研究者たちが悩んでいたこと

昔から、数学者たちはこう考えていました。
「ブロックの数が無限に増えたとき、連結部品の数の『密度』は、ある一定の値に落ち着くのではないか？」

• k=2 のとき（昔の発見）： 答えは「1/6」だと分かりました。
• k=3, 4 のとき： 別の数学者たちが「1/5」「7/36」など、それぞれの答えを見つけました。
• k が大きい偶数のとき： 以前、レトツァーとスゲグリアという研究者たちが、「ブロックの繋ぎ方（r）が非常に巨大なら、答えは1/(r²-r) というきれいな数字になるよ」と証明しました。

しかし、彼らの証明には大きな欠点がありました。
**「r がどれくらい巨大ならいいの？」という問いに対して、彼らは「k の 1.5 乗（k の 3/2 乗）くらい巨大なら大丈夫」と言っていたのです。
例えば、k=100 なら、r は 1000 以上必要、というように、「あまりに巨大すぎる条件」**でした。

3. この論文のすごいところ：「もっと小さな条件で OK！」

この論文の著者（王さんと曾さん）は、**「そんなに巨大な r でなくても、もっと小さな r でも同じ答えが成り立つよ！」**と証明しました。

彼らが使った新しい方法は、**「重み付けの魔法」と「賢い合体」**です。

魔法の道具：重み付け（Weighting）

彼らは、レゴの城の「どの 2 つのブロックが繋がっているか」に**「重み（ポイント）」**を付けました。

• 「すでに 1 回繋がっているペア」には 1 ポイント。
• 「2 回繋がっているけど、1 回目は繋がっていないペア」には、少し少ないポイント。
• それ以外は 0 ポイント。

そして、**「どんなに城を大きくしても、1 つのペアに付く合計ポイントは 1 を超えない」**というルールを証明しました。
これにより、「連結部品の総数」を「ポイントの総和」で抑え込むことができるのです。

賢い合体：「ダイヤモンド」の発見

彼らは、レゴの城の中に**「ダイヤモンド（ひし形）」**のような特別な構造を見つけました。

• この「ダイヤモンド」は、城の他の部分と**「2 つの点」**でしか繋がっていません。
• この性質を利用すると、城を大きくしても、**「禁止された形（NG な小さな城）」**ができてしまうことを防げる、という仕組みを見つけました。

4. 結果：条件が劇的に改善された！

彼らの証明によって、**「r がどれくらい大きければいいか」**という条件が、劇的に楽になりました。

• 以前の条件（レトツァーら）： $r \ge \sqrt{2} \cdot k^{3/2}$ （k の 1.5 乗くらい必要）
• 今回の条件（王・曾）： $r \ge 2 + \sqrt{1.5k - 4}$ （k の 0.5 乗、つまり平方根くらいで OK）

【イメージ】

• 以前は、「k=100 なら、r は 1000 以上必要！」と言われていたのが、
• 今回は、「k=100 なら、r は 15 くらいあれば十分！」と言えるようになったのです。

5. まとめ：なぜこれが重要なのか？

この研究は、**「複雑なルール（禁止された形）がある世界でも、ある程度の大きさになれば、最適な構造はシンプルで美しい形（1/(r²-r)）に落ち着く」**ことを示しました。

さらに、**「その『ある程度の大きさ』のハードルを、以前よりも遥かに低くした」**という点が画期的です。
まるで、「巨大な城を作るには、まず 1000 階建てのビルが必要だと言われていたが、実は 15 階建てのビルでも作れることがわかった！」という発見と同じくらい、驚きと喜びをもたらすものです。

この発見は、将来、より複雑なパズルを解くための「新しい道具箱」を提供することになり、数学の分野で大きな一歩を踏み出したと言えます。

技術概要

1. 問題設定 (Problem Setting)

背景:
$r$-一様超グラフ（$r$-グラフ）$H$ において、$k$ 個の辺が $s$ 個以下の頂点を張るような部分超グラフが存在しない場合、その超グラフを $F^{(r)}(s, k)$-フリーと呼びます。$f^{(r)}(n; s, k)$ は、$n$ 個の頂点を持つ $F^{(r)}(s, k)$-フリーな $r$-グラフの辺数の最大値（Turán 数）を表します。

Brown-Erdős-Sós 予想:
1973 年に提唱されたこの予想は、$k \ge 2$ に対して、極限 $\lim_{n \to \infty} n^{-2} f^{(3)}(n; k+2, k)$ が存在することを主張しています。

• $k=2$ の場合、この極限は $1/6$ であることが証明されています。
• $k=3$ の場合、$1/5$ であることが証明されています。
• 一般の $k$ については、Delcourt と Postle によって極限の存在自体は証明されましたが、その正確な値は特定されていませんでした。

本研究の対象:
より一般的な次数 $r \ge 3$ に対して、$s = (r-2)k + 2$ の場合の極限値
$$\pi(r, k) := \lim_{n \to \infty} n^{-2} f^{(r)}(n; (r-2)k + 2, k)$$
の正確な値と、その値が $\frac{1}{r^2-r}$ となるための最小の次数 $r_0(k)$ の条件を明らかにすることです。
これまでに、$k$ が小さい値（$k \le 8$）や、$r$ が非常に大きい場合（Letzter と Sgueglia の結果：$r \ge \sqrt{2k^{3/2}} + 2$）には $\pi(r, k) = \frac{1}{r^2-r}$ であることが示されていましたが、$r$ の条件を緩和することが課題でした。

2. 主要な貢献と結果 (Key Contributions and Results)

主定理 (Theorem 1.2):
任意の偶数 $k \ge 4$ と整数 $r$ に対して、以下の条件が成り立つ場合、極限値は正確に $\frac{1}{r^2-r}$ となります。
$$r \ge \sqrt{\frac{3}{2}k - 4} + 2$$
すなわち、
$$\pi(r, k) = \frac{1}{r^2 - r}$$

既存結果との比較:

• Letzter と Sgueglia (2023) は、$r \ge \sqrt{2k^{3/2}} + 2$ の条件下で同様の結果を証明していました。
• 本研究は、$r$ の下限を $O(k^{1/2})$ から $O(k^{3/2})$ に改善し、より広い範囲の $r$ に対して正確な値を決定しました。
• 具体的には、$k=4$ の場合 $r_0(4)=4$ となり、既知の結果と一致します。$k=6, 8$ の場合、本研究では $r_0(k) \le 5$ を示しています（最適値 $r_0(k)=4$ は今後の課題ですが、改善は顕著です）。

3. 手法 (Methodology)

本研究は、Glock, Joos, Kim, K"uhn, Lichev, Pikhurko, R"odl, Sun などの先行研究（特に [8, 9, 13]）で用いられた「マージ（結合）と重み付け」のアプローチを拡張・改良したものです。

証明の概要:

1. 下限の証明 (Lower Bound):

   • 単一の辺からなる $r$-グラフ $F$ を用いて、Lemma 3.1 を適用することで、$\pi(r, k) \ge \frac{1}{r^2-r}$ が示されます。これは既知の構成法に基づいています。

2. 上限の証明 (Upper Bound) - 核心部分:

   • 構造の分析: $G^{(r)}_k$-フリーな超グラフ $G$ において、辺集合を「1-クラスター（連結成分）」に分割し、さらに「2-クラスター」へとマージするプロセスを定義します。
   • Property P の導入: マージされたクラスター $F$ が特定の構造的条件（Property P）を満たすかどうかを分析します。Property P は、クラスターが「柔軟なダイヤモンド（flexible diamond）」と呼ばれる特定の部分構造を含み、特定の辺数と頂点数の関係を満たすことを要求します。
   • 構造定理 (Theorem 3.6, 3.7, 3.8): $G^{(r)}_k$-フリーであるという制約から、マージされたクラスター $F$ が Property P を満たす場合、その辺数 $|F|$ とマージ回数 $m(F)$ の間に $|F| \ge 2m(F) - k + 3$ という強い不等式が成り立つことを証明します。
   • 重み付けの割り当て (Weight Assignment):
     • 各頂点対 $xy$ に対して、それを「主張（claim）」するクラスターに基づいて重み $w(xy)$ を定義します。
     • 1-claim（1 個の辺で張られる）と 2-claim（2 個の辺で張られる）の条件に基づき、重みを $1$または$\frac{2}{k-2}$ に設定します。
     • Lemma 3.13: 任意の頂点対 $xy$ に対して、割り当てられた総重み $w(xy) \le 1$ であることを示します（これはマージの規則と $G^{(r)}_k$-フリー性による矛盾回避から導かれます）。
   • 重みと辺数の関係 (Lemma 3.14):
     • クラスター $F$ 内の総重み $w(F)$ と辺数 $|F|$ の関係を評価します。
     • 条件 $r \ge \sqrt{\frac{3}{2}k - 4} + 2$ を用いることで、$w(F) \ge \binom{r}{2} |F|$ が成り立つことを示します。
   • 結論: 全頂点対の重みの和は $\binom{n}{2}$ 以下であり、かつ各クラスターの重みは辺数の $\binom{r}{2}$ 倍以上であるため、辺数の総和 $|G|$ は $\frac{1}{\binom{r}{2}} \binom{n}{2} \approx \frac{1}{r^2-r} n^2$ 以下に抑えられます。

4. 技術的な詳細と革新点

• Property P の利用: 先行研究では複雑な局所構造の扱いが必要でしたが、本研究では「Property P」を満たす構造に焦点を当てることで、マージプロセスの振る舞いを統制し、より緩やかな $r$ の条件で不等式を成立させることに成功しました。
• 重み付け関数の最適化: $k$ が偶数であることと、$r$ の具体的な値（$\sqrt{3k/2 - 4} + 2$）を組み合わせることで、重みの合計が 1 を超えないように調整しつつ、辺数に対する重みの比率を最大化するバランスを見出しました。
• Case 分析の精密化: Theorem 3.7 の証明において、$m(F)$（マージ回数）が $k$ より小さい場合と大きい場合で分けて議論し、特に $m(F) \ge k$ の場合に Theorem 3.7 の不等式が有効に働くことを示すことで、$r$ の条件を厳密に導出しています。

5. 意義 (Significance)

• Brown-Erdős-Sós 問題の進展: 偶数 $k$ に対する極限値の正確な値を、より広い次数 $r$ の範囲で決定しました。これは、極値超グラフ理論における長年の課題に対する重要な進展です。
• $r_0(k)$ の改善: Letzter と Sgueglia が示した $r_0(k) = O(k^{3/2})$ という条件を、$r_0(k) = O(k^{1/2})$ に改善しました。これは、$k$ が増大しても、比較的低い次数 $r$ で既に極限値が安定することを示唆しており、理論的な理解を深めました。
• 手法の一般化可能性: 用いられた「マージと重み付け」の手法は、他の極値問題や、$k$ が奇数の場合、あるいはより複雑な配置問題への応用が期待されます。

結論

この論文は、偶数 $k$ に対する Brown-Erdős-Sós 問題の極限値 $\pi(r, k)$ が、$r \ge \sqrt{\frac{3}{2}k - 4} + 2$ の条件下で $\frac{1}{r^2-r}$ であることを証明しました。これは既存の条件を大幅に緩和するものであり、超グラフの極値理論における重要なマイルストーンです。