2025-11-12T07:25:09.921673

Bipartite Turán number of paths and other trees

Bonamy, Leclere, Picavet
We solve a recent question of Caro, Patkós and Tuza by determining the exact maximum number of edges in a bipartite connected graph as a function of the longest path it contains as a subgraph and of the number of vertices in each side of the bipartition. This was previously known only in the case where both sides of the bipartition have equal size and the longest path has size at most $5$. We also discuss possible generalizations replacing "path" with some specific types of trees.
academic

二部グラフのTurán数：経路および他の木

基本情報

  • 論文ID: 2511.07374
  • タイトル: Bipartite Turán number of paths and other trees
  • 著者: Marthe Bonamy、Théotime Leclere、Timothé Picavet
  • 所属機関: CNRS、LaBRI、ボルドー大学；パリ・サクレーENS
  • 分類: math.CO（組合数学）、cs.DM（離散数学）
  • 発表日: 2025年11月11日
  • 論文リンク: https://arxiv.org/abs/2511.07374

要約

本論文は、Caro、Patkós、Tuzaが最近提起した問題を完全に解決した：二部連結グラフにおける辺数の正確な最大値を決定する問題である。この最大値は、グラフ内の最長経路の長さと二部分割の両側の頂点数の関数である。従来、この問題は二部分割の両側のサイズが等しく、最長経路の長さが最大5である場合にのみ既知であった。本論文はまた、「経路」を特定の種類の木に置き換える可能な一般化についても論じている。

研究背景と動機

問題の背景

  1. 古典的なTurán問題：Turánの定理は、与えられた位数の完全部分グラフを含まないn頂点グラフの最大辺数を決定し、禁止部分グラフの極値問題の体系的研究を開始した。
  2. Erdős-Stone定理の限界：この定理は、すべての非二部禁止グラフのTurán数を漸近的に与えるが、二部グラフの場合には情報を提供しない。
  3. 二部グラフの特殊性：二部グラフのTurán問題は依然として未解決であり、複数の中核的な予想を生み出した。最も有名なのはErdős-Sós予想である：k個の頂点を持つ木を除外するn頂点グラフは最大(k-2)n/2本の辺を持つ。
  4. 連結二部グラフの研究：Caro、Patkós、Tuza CPT25は最近、宿主グラフが二部グラフかつ連結である場合に焦点を当て、exb,c(a,b,H)という記号を導入した。これは部分サイズがaおよびbで、Hを部分グラフとして含まない連結二部グラフの最大辺数を表す。

研究の動機

  • 既知結果の限界：CPT25は6個以下の頂点を持つすべての木、双星、および特定のクモグラフのみを解決した。特に、exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1のみが既知である。
  • 未解決問題：任意の経路Pₖに対してexb,c(n,n,Pₖ)を決定する必要がある。少なくとも漸近値を与える必要がある。
  • 一般化の必要性：特定の木族のexb,c値を研究する必要がある。

核心的貢献

  1. 経路問題の完全解決：すべての経路Pₖに対して、exb,c(a,b,Pₖ)の正確な値を与える。漸近値だけでなく、不均衡な二部グラフにも適用される（主定理1.5）。
  2. ほうき図への拡張：ほうき図Sp,d*（経路長pとd個の枝を持つ星の組み合わせ）に対して、星が経路より大きい場合に正確な値を与える（定理1.6）。
  3. 上界結果：星が経路サイズの最大半分である場合、上界を提供する（定理1.7）。
  4. 技術的革新：連結二部グラフを扱うための新しい技術を開発した。これには、重要な頂点の存在性補題と帰納的枠組みが含まれる。

方法の詳細

タスク定義

定義1.1：固定整数a、bおよびグラフHに対して、exb,c(a,b,H)は部分サイズがaおよびbで、Hを部分グラフとして含まない連結二部グラフの最大辺数である。

本論文は主に以下を研究する：

  • 入力：経路長k、二部分割サイズa、b
  • 出力：exb,c(a,b,Pₖ)の正確な値
  • 制約：グラフは連結、二部、Pₖを部分グラフとして含まない

核心定理

定理1.5（主要結果）：すべてのk ≥ 3およびb ≥ a ≥ kに対して、 exb,c(a,b,P2k)=exb,c(a,b,P2k−1)=(k−2)(b−1)+a\text{ex}_{b,c}(a,b,P_{2k}) = \text{ex}_{b,c}(a,b,P_{2k-1}) = (k-2)(b-1) + a

この公式は以下を示唆する：

  • 奇数および偶数長の経路は同じTurán数を持つ
  • 辺数は大きい部分bに関して線形に増加し、係数は(k-2)
  • 加法補正項aが存在する

証明アーキテクチャ

1. 下界構成（第2節）

命題2.1は構成的証明を提供する：

グラフGを構成する。二部分割はA = {u₁,...,uₐ}およびB = {v₁,...,vᵦ}：

  • A内の最初のk-2個の頂点はB内のすべての頂点と完全に接続される（Kₖ₋₂,ᵦを形成）
  • A内の残りのa-(k-2)個の頂点は葉として機能し、すべてB内の特定の頂点に接続される

辺数の計算： ∣E(G)∣=b(k−2)+(a−(k−2))=(k−2)(b−1)+a|E(G)| = b(k-2) + (a-(k-2)) = (k-2)(b-1) + a

P₂ₖ₋₁-free性質の証明：

  • 完全二部グラフKₖ₋₂,ᵦの最長経路は2k-3個の頂点を持つ
  • 追加された葉は経路を延長できない。なぜなら、それらはすべて次数1の頂点だから

2. 上界証明（第3節）

帰納法を採用し、3つの補題が重要である：

補題3.2（小次数頂点の存在性）：大きい部分Bに次数≤k-2を持ち、削除後も連結を保つ頂点xが存在する。

証明の考え方：

  • DFS木を使用してB内の葉bを見つける
  • d(b) ≤ k-2ならば、x = bとする
  • d(b) = k-1ならば、経路長は必ず2k-2であり、ループを形成する
  • この場合、別の次数≤k-2の頂点b'を見つけることができる

補題3.3（均衡グラフの削除可能な頂点対）：均衡二部グラフに対して、d(x) + d(y) ≤ k-1を満たし、削除後も連結かつ均衡を保つ2つの頂点x、yが存在する。

証明は最長経路Pの端点分析を使用する：

  • 端点が異なる部分にある場合、直接使用できる可能性がある
  • そうでない場合、DFS木を使用して適切な葉のペアを見つける

補題3.4（基本ケース）：a = b = kのとき、|E(G)| ≤ (k-1)² + 1。

証明は帰納法を採用し、重要な観察：

  • 非切断点の最小次数頂点xを見つける
  • xを削除した後、残りのグラフの構造を分析する
  • P₂ₖ-free性質を利用して次数と構造を制限する

主定理の証明：

  • b > aの場合：補題3.2を使用して1つの頂点を削除し、帰納する
  • a = b > kの場合：補題3.3を使用して2つの頂点を削除し、帰納する
  • a = b = kの場合：補題3.4を使用する

ほうき図の結果

定理1.6：k、d ≥ 2に対して、n ≥ d²/2かつd > 2kのとき、 exb,c(n,n,S2k,d)=exb,c(n,n,S2k+1,d)=nd\text{ex}_{b,c}(n,n,S_{2k,d}) = \text{ex}_{b,c}(n,n,S_{2k+1,d}) = nd

重要な技術補題：

補題4.1：グラフに2k長経路の端点ではない頂点が存在する場合、|E(G)| ≤ (k-1)(b+a)

補題4.2：|E(G)| ≥ k(b+a)+1ならば、すべての頂点の次数は最大k+d-1

証明はこれらの補題を組み合わせ、最大次数頂点とその隣接点を削除し、連結性と次数制約を利用して矛盾を得る。

実験設定

純粋な理論数学論文として、本論文は実験部分を含まない。すべての結果は厳密な数学的証明によって得られている。

実験結果

主要結果の検証

経路の正確な公式：

  • P₅およびP₆に対して：exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
    • 公式を使用：k=3のとき、(3-2)(n-1)+n = n-1+n = 2n-1 ✓
  • 一般的なPₖに対して：公式は、不均衡な二部グラフを含むすべてのケースの正確な値を与える

ほうき図の結果：

  • 星部分が支配的である場合（d > 2k）、Turán数はnd
  • これは最大次数制約と一致している

既知結果との比較

  1. 命題1.2の一般化：本論文の結果はCPT25のexb,c(n,n,P₅) = 2n-1を完全に含み、一般化している
  2. 一般性の向上：
    • 均衡グラフから不均衡グラフへの拡張
    • 特定の小さい経路から任意の経路への拡張
    • 漸近結果から正確な公式への拡張

関連研究

古典的結果

  1. Turánの定理 Tur45：完全グラフの極値問題
  2. Erdős-Stone定理 ES46：非二部グラフの漸近Turán数
  3. Gallai-Erdős GE59：固定サイズの経路を除外する連結グラフの漸近結果
  4. Gyárfás-Rousseau-Schelp GRS84：固定サイズの経路を除外する二部グラフの正確なTurán数

直接関連する研究

Caro-Patkós-Tuza CPT25：

  • exb,c記号を導入
  • 小さい木のケース（≤6頂点）を解決
  • 双星と特定のクモグラフを解決
  • 本論文が解決する問題を提起

独立した研究

He-Salia-Zhu HSZ25：著者は同じ日に提出された類似の進展に関する独立した研究があることを言及している

結論と考察

主要な結論

  1. 質問1.3への完全な回答：すべての経路Pₖに対してexb,c(n,n,Pₖ)の正確な値を与え、質問が要求する漸近値を超えている
  2. 質問1.4への部分的な回答：ほうき図族に対して、特定のパラメータ範囲内で正確な値または上界を与える
  3. 方法論的貢献：連結二部グラフの極値問題を扱うための新しい技術的枠組みを開発した

限界

  1. ほうき図の制限：
    • 定理1.6はd > 2kおよびn ≥ d²/2を要求する
    • 定理1.7は上界のみを与え、正確な値ではない
    • 中間的なケース（d ≈ k）は完全に解決されていない
  2. 木の一般的なケース：経路とほうき図のみを扱い、より一般的な木族は依然として未解決
  3. 技術的限界：特定の証明ステップは特定の構造的性質に依存し、より複雑な禁止部分グラフへの一般化が困難な可能性がある

今後の方向

  1. ほうき図の結果の完善：すべてのパラメータ範囲の正確な値を決定する
  2. 他の木族への拡張：
    • クモグラフの完全な特性化
    • 他の特殊な木構造
  3. 不均衡ケースの深い研究：本論文はa ≠ bのケースを扱っているが、より精密な結果が存在する可能性がある
  4. 計算複雑性：与えられたグラフがTurán界に達しているかどうかを判定するアルゴリズム問題を研究する

深い評価

長所

  1. 未解決問題の完全解決：
    • 質問1.3に回答するだけでなく、要求されたものより強い正確な公式を与える
    • 不均衡な二部グラフへの拡張により、結果の一般性を強化する
  2. 証明技術の優雅さ：
    • 下界構成は簡潔で明確
    • 上界証明の帰納的構造は明確
    • 重要な補題（3.2、3.3、3.4）の陳述と証明は精密
  3. 結果の完全性：
    • 経路に対して、すべてのパラメータの正確な公式を与える
    • 公式形式は簡潔：(k-2)(b-1)+a
    • 奇数および偶数長の経路を統一的に扱う
  4. 執筆品質：
    • 論文の構造は明確で、論理は厳密
    • 重要なステップは詳細な副命題によってサポートされている
    • 図（図1など）は構成の理解を助ける
  5. 技術的革新：
    • 補題3.2は小次数非切断点の存在性に関する重要な洞察
    • 均衡グラフにおける削除可能な頂点対の特性化（補題3.3）は独立した価値を持つ
    • DFS木の使用は証明全体に及び、古典的なツールの有効な応用を示す

不足

  1. ほうき図の結果が不完全：
    • 定理1.6と1.7の間にパラメータギャップが存在する
    • 定理1.7は上界2nk+1のみを与え、可能な正確な値との差は不明
    • 条件n ≥ d²/2は技術的に見え、最適ではない可能性がある
  2. 基本ケースの証明が複雑：
    • 補題3.4（a=b=kのケース）の証明は大きなスペースを占める
    • 複数の副命題（主張3.11-3.13）が必要
    • より直接的な議論が存在する可能性がある
  3. 一般化の限定性：
    • 方法は経路とほうき図の特殊な構造に高度に依存している
    • 一般的な木に対して、これらの技術をどのように適用するかは不明確
    • 可能な統一的枠組みについての議論がない
  4. 独立した研究との関係：
    • HSZ25の独立した研究に言及しているが、詳細な比較がない
    • 2つの論文の技術的方法が同じかどうかは不明確

影響力

  1. 理論的貢献：
    • 明確に提起された未解決問題を完全に解決
    • 連結二部Turán問題に新しい技術的ツールを提供
    • 結果の正確性により、この分野のベンチマークとなる
  2. 方法論的価値：
    • 帰納的枠組みは他の禁止部分グラフ問題に適用可能
    • 重要な補題は他の文脈で有用である可能性がある
  3. 後続研究：
    • ほうき図の完全な特性化の問題を自然に引き出す
    • 他の木族のexb,c値の研究を刺激する
    • 非連結ケースの研究を刺激する可能性がある
  4. 検証可能性：
    • 純粋な理論的結果として、証明をチェックすることで検証可能
    • 構成は明示的で、理解と検証が容易
    • 公式は簡潔で、応用と引用が容易

適用シーン

  1. 理論研究：
    • 極値グラフ理論研究者の参考結果
    • Turán型問題の技術的ソース
    • 連結性制約下の極値問題のケーススタディ
  2. 関連問題：
    • Erdős-Sós予想の研究に対する可能な洞察
    • 他の木のTurán数の比較を提供
    • 連結二部グラフの構造的性質の研究
  3. 教育的価値：
    • 極値組合論における帰納法の応用を示す
    • DFS木と経路分析の例
    • 上界と下界の一致の完全なケース

参考文献（主要文献）

  1. CPT25 Caro、Patkós、Tuza：二部グラフのTurán数 - 本論文が解決する問題を提起
  2. Tur45 Turán：グラフ理論の極値問題について - Turán問題の基礎を確立
  3. ES46 Erdős、Stone：線形グラフの構造について - Erdős-Stone定理
  4. GRS84 Gyárfás、Rousseau、Schelp：二部グラフの経路に関する極値問題 - 二部グラフの経路の正確なTurán数（連結性要件なし）
  5. HSZ25 He、Salia、Zhu：長いサイクルと経路に対する連結二部Turán問題 - 独立した関連研究

総合評価

これは組合数学の高品質な論文であり、明確に提起された未解決問題を完全に解決し、要求されたものより強い結果を与えている。証明技術は優雅で革新的であり、結果は完全性と正確性を持つ。木の一般的なケースへの一般化に関してはまだ作業が必要であるが、経路のケースでは決定的な答えを提供している。この研究は連結二部Turán問題の研究に実質的な貢献をし、この分野の重要な参考文献になることが予想される。