$K_{2, t+1}$-free graphs containing an optimal number of $K_{t, t}$'s

技術要約：最適な数の $K_{t,t}$ を含む $K_{2,t+1}$ フリーグラフ

問題設定
本論文は、一般化されたテューラン数 $\text{ex}(n, H, F)$ を扱う。これは、$n$ 個の頂点を持つ $F$ フリーグラフの中に存在しうる $H$ のコピーの最大数を表す。具体的には、著者らは $H = K_{t,t}$ かつ $F = K_{2,t+1}$ の場合を調査している。目的は、$\text{ex}(n, K_{t,t}, K_{2,t+1})$ の漸近的挙動を決定することである。

最近の研究において、Pohoata, Tidor, および Yu は、すべての整数 $t \ge 3$ に対して $\text{ex}(n, K_{t,t}, K_{2,t+1}) = \Theta_t(n^2)$ であることを確立したが、彼らの証明は確率論的手法と部分空間回避集合に依存しており、係数が必ずしも最適ではない下界を与えていた。本論文は、明示的な構成を用いることで、特定の $n$ および $t$ の値に対する精密な漸近公式を提供することを目的としている。

手法
著者らは、有限体と線形化多項式に基づいた、決定論的かつ代数的なグラフ構成を採用している。

1. グラフ構成 ($\Gamma_{t,e}$):

   • $t$ を素数冪とし、$e > 1$ を整数とする。$q = t^e$ と定義する。
   • $L$ を $\mathbb{F}_q[x]$ 上の $\mathbb{F}_t$-線形化多項式とし、その核（kernel）の次元を 1 とする。像空間 $R_L$ のサイズは $t^{e-1}$ である。
   • 頂点集合は $V = \mathbb{F}_q \times R_L$ と定義され、これにより $n = q \cdot t^{e-1} = t^{2e-1}$ 個の頂点が得られる。
   • 異なる 2 頂点 $(v_1, v_2)$ と $(w_1, w_2)$ が隣接するための必要十分条件は、$v_2 + w_2 = L(v_1 w_1)$ である。単純グラフを保証するため、この方程式によって導かれる自己ループは除去される。

2. 上界の導出:

   • 著者らはまず、$\text{ex}(n, K_{t,t}, K_{2,t+1})$ に対する精密な上界を確立する。
   • この議論は、$K_{2,t+1}$ フリーグラフにおいては、任意の 2 頂点が高々 $t$ 個の共通隣接点を持つという事実に依拠している。
   • 頂点のペアを数え、それらを構成するペアを通じて $K_{t,t}$ が何回カウントされるかを分析することで、以下の境界を導出する：
     $$\text{ex}(n, K_{t,t}, K_{2,t+1}) \le \frac{\binom{n}{2}}{2\binom{t}{2}}$$

3. 構成の構造解析:

   • $K_{2,t+1}$ フリー性: 著者らは、$\Gamma_{t,e}$ が $K_{2,t+1}$ を含まないことを証明する。任意の 2 頂点について、共通の隣接点の数は $L$ に関する線形方程式の解の数によって決定される。$L$ は $t$-対1 の写像であるため、共通の隣接点は高々 $t$ 個である。
   • $K_{t,t}$ の形成: 証明の核心は、非隣接な頂点の分析にある。著者らは、異なる第 1 座標を持つ任意の非隣接な 2 頂点が、濃度 $t$ の 2 つの集合 $M$ と $N$ を一意に定義することを示す。
     • $N$ は共通の隣接点の集合（$\mathbb{F}_t$-直線）である。
     • $M$ は、その 2 頂点を含む $\mathbb{F}_t$-直線である。
     • $M$ のすべての頂点は、$N$ のすべての頂点に対して代数的に隣接している。
   • もし $M \cap N = \emptyset$ であれば、$M \cup N$ によって誘導される部分グラフは $K_{t,t}$ となる。もし $|M \cap N| = 1$ であれば、その構造は 3 部グラフの完全グラフ $K_{1, t-1, t-1}$ を形成する。

主要な貢献と結果
主な貢献は、無限個の $n$ に対して、理論的な上界（低次項を除いて）を達成するグラフ族の明示的な構成を提供したことである。

• 定理 1.1: $t$ が素数冪であり、$n = t^{2e-1}$（ここで $e > 1$ は整数）であるとき、一般化されたテューラン数は以下のようになる：
  $$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
• 以前の境界との比較: 本論文は、[5] による以前の最良の下界が $(1-o(1)) \frac{n^2}{4t^2 t!}$ という形式であったことに触れている。今回の結果は、$t > 5$ の素数冪に対して、この係数を大幅に改善している。
• 非最適ケースの無視可能性: 著者らは、$K_{1, t-1, t-1}$（$|M \cap N| = 1$ の場合）となる構成の数が、$K_{t,t}$ の総数（$O(n^2)$）に対して無視できる程度（$O(n)$）であることを示し、これにより $K_{t,t}$ カウントの漸近的な支配を保証している。

意義と主張
本論文は、以前利用可能であった確率論的な存在証明とは対照的に、「単純かつ完全に明示的な構成」を、（希薄ではあるものの）無限の $n$ の集合に対して提供したと主張している。この構成は、多色 Ramsey 数に関連して Lazebnik と Mubayi によって研究されたグラフと同型であるが、本論文ではこれらを一般化されたテューラン問題に特化して適用している。

著者らは、導出された上界が、構成された特定の素数冪の場合だけでなく、すべての $n$ に対してタイトであるという予想を述べている：
$$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
本研究は、二部グラフの一般化されたテューラン数の成長率の理解を、オーダーの評価から、特定の領域における精密な漸近定数へと精緻化する役割を果たしている。