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

Bipartite Turán number of paths and other trees

基本信息

  • 论文ID: 2511.07374
  • 标题: Bipartite Turán number of paths and other trees
  • 作者: Marthe Bonamy, Théotime Leclere, Timothé Picavet
  • 单位: CNRS, LaBRI, Université de Bordeaux; ENS Paris-Saclay
  • 分类: 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ᵦ}：

  • 前k-2个A中的顶点与所有B中的顶点完全连接（形成Kₖ₋₂,ᵦ）
  • 剩余的a-(k-2)个A中的顶点作为叶子，都连接到一个特定的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.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（平衡图的可删除顶点对）：对于平衡二部图，存在两个顶点x, y使得d(x) + d(y) ≤ k-1且删除后保持连通和平衡。

证明使用最长路径P的端点分析：

  • 如果端点在不同部分，可能可以直接使用
  • 否则使用DFS树找到合适的叶子配对

引理3.4（基础情况）：当a = b = k时，|E(G)| ≤ (k-1)² + 1。

证明采用归纳法，关键观察：

  • 找到非割点的最小度顶点x
  • 删除x后分析剩余图的结构
  • 利用P₂ₖ-free性质限制度数和结构

主定理证明：

  • 如果b > a：使用引理3.2删除一个顶点，归纳
  • 如果a = b > k：使用引理3.3删除两个顶点，归纳
  • 如果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. 完全解答Question 1.3：给出了所有路径Pₖ的exb,c(n,n,Pₖ)的精确值，超越了问题要求的渐近值
  2. 部分解答Question 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. 完全解决开放问题：
    • 不仅回答了Question 1.3，而且给出了比要求更强的精确公式
    • 扩展到不平衡二部图，增强了结果的一般性
  2. 证明技术优雅：
    • 下界构造简洁明了
    • 上界证明的归纳结构清晰
    • 关键引理（3.2, 3.3, 3.4）的陈述和证明都很精炼
  3. 结果的完整性：
    • 对于路径，给出了所有参数的精确公式
    • 公式形式简洁：(k-2)(b-1)+a
    • 统一处理了奇数和偶数长度路径
  4. 写作质量：
    • 论文结构清晰，逻辑严密
    • 关键步骤有详细的子命题支撑
    • 图示（如Figure 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的情况）的证明占据较大篇幅
    • 需要多个子命题（Claims 3.11-3.13）
    • 可能存在更直接的论证
  3. 推广性有限：
    • 方法高度依赖于路径和扫帚图的特殊结构
    • 对于一般树，不清楚如何应用这些技术
    • 没有讨论可能的统一框架
  4. 与独立工作的关系：
    • 提到HSZ25的独立工作但未详细比较
    • 不清楚两篇论文的技术方法是否相同

影响力

  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: Bipartite Turán number of trees - 提出了本文解决的问题
  2. Tur45 Turán: On an extremal problem in graph theory - 奠定了Turán问题的基础
  3. ES46 Erdős, Stone: On the structure of linear graphs - Erdős-Stone定理
  4. GRS84 Gyárfás, Rousseau, Schelp: An extremal problem for paths in bipartite graphs - 二部图中路径的精确Turán数（无连通性要求）
  5. HSZ25 He, Salia, Zhu: The connected bipartite Turán problem for long cycles and paths - 独立的相关工作

总体评价

这是一篇高质量的组合数学论文，完全解决了一个明确提出的开放问题，并给出了比要求更强的结果。证明技术优雅且创新，结果具有完整性和精确性。虽然在树的一般情况推广方面还有工作要做，但论文在路径的情况下提供了决定性的答案。这项工作为连通二部Turán问题的研究做出了实质性贡献，预期会成为该领域的重要参考文献。