Large cliques in graphs with forbidden semi-induced structures

基本信息

• 论文ID: 2511.13073
• 标题: Large cliques in graphs with forbidden semi-induced structures
• 作者: Nannan Chen (Shandong University & IBS), Yulai Ma (Nankai University), Fan Yang (Shandong University & IBS)
• 分类: math.CO (Combinatorics)
• 提交时间: 2025年11月17日
• 论文链接: https://arxiv.org/abs/2511.13073

摘要

本文研究了禁止半导出子结构的图中大团的存在性问题。Holmsen在2022年证明了任何包含至少 $c\binom{n}{r}$ 个 $r$-团但不包含导出完全 $r$-部图 $K_{2,\ldots,2}$ 的图必定包含阶为 $Ω(c^{2^{r-1}}n)$ 的团。本文通过禁止与 $K_{2,\ldots,2}$ 相关的半导出子结构，证明了每个包含至少 $c\binom{n}{r}$ 个 $K_r$ 副本的 $n$ 顶点图 $G$ 必定包含阶为 $Ω(cn)$ 的团。该结果将Holmsen界中对 $c$ 的依赖从 $c^{2^{r-1}}$ 改进为关于 $c$ 的线性，且仅需禁止有界数量的结构。此外，该方法自然地与VC维概念相联系。

研究背景与动机

问题背景

1. 经典Turán理论：Turán定理及其推广（Erdős-Stone-Simonovits定理）研究了禁止非导出子图的极值问题。对于色数 $χ(H) ≥ 3$ 的图 $H$，禁止 $H$ 作为子图会使极值图渐近为 $(χ(H)-1)$-部图，从而团数被常数界限。
2. 导出子图的情形：当禁止导出子图时，情况完全不同。Gyárfás, Hubenko和Solymosi (2002)证明了如果 $n$ 顶点图 $G$ 有至少 $c\binom{n}{2}$ 条边且不包含导出 $K_{2,2}$，则 $ω(G) ≥ \frac{c^2}{10}n$。
3. 弦图的紧界：弦图（禁止长度至少为4的导出圈）达到了更优的界：$ω(G) ≥ (1-\sqrt{1-c})n$，当 $c$ 很小时为 $Ω(cn)$。
4. Holmsen的推广：Holmsen (2020)将 $K_{2,2}$ 情形推广到多部版本，证明了禁止导出 $K_r[2]$（$K_r$ 的2-膨胀）的图包含阶为 $Ω(c^{2^{r-1}}n)$ 的团。

研究动机

尽管Holmsen的结果关于 $n$ 是线性的，但其对 $c$ 的界随 $r$ 增长而迅速恶化。本文的核心问题是：能否类似于从定理1.1到定理1.2的改进，通过禁止更多（但有界数量）的结构来改善Holmsen界？

重要性

• 该问题连接了极值图论与抽象Helly定理
• 对理解导出子图禁止条件与团数的关系具有基础意义
• 揭示了VC维在图结构中的作用

核心贡献

1. 主要定理：证明了对于包含至少 $c\binom{n}{r}$ 个 $K_r$ 副本的导出 $K_r^{[2]}$-free图 $G$，有 $ω(G) ≥ \frac{c}{18r}n$（定理1.5）
2. 界的改进：将Holmsen的 $Ω(c^{2^{r-1}}n)$ 界改进为 $Ω(cn)$，实现了对 $c$ 的线性依赖
3. 有界禁止结构：仅需禁止至多 $2^{\binom{r}{2}}$ 个导出子结构（相比弦图的无穷多个）
4. VC维方法：建立了半导出子图与VC维的自然联系，推广了已有的双导出子图理论
5. 结构洞察：揭示了即使禁止远少于弦图的结构数量，仍能保证线性大小的团

方法详解

任务定义

输入：$n$ 顶点图 $G$，满足：

• 包含至少 $c\binom{n}{r}$ 个 $K_r$ 副本（$c > 0$ 为常数）
• 导出 $K_r^{[2]}$-free（不包含 $K_r^{[2]}$ 中任何图作为导出子图）

输出：证明 $G$ 包含阶至少为 $\frac{c}{18r}n$ 的团

关键定义：

• $K_r[2]$：$K_r$ 的2-膨胀，将每个顶点替换为大小为2的独立集
• $K_r^{[2]}$：$K_r[2]$ 的子图族，其边集形式为 $(E(K_r[2])\backslash E(K_{U'})) \cup E'$，其中 $U' = \{u'_1, \ldots, u'_r\}$ 是每个部分的第二个顶点集，$E' \subseteq E(K_{U'})$

核心架构

本文证明分为三个关键步骤：

1. VC维界（Claim 2.3）

核心引理：导出 $K_r^{[2]}$-free图的极大团集合 $MC(G)$ 的VC维至多为 $r-1$。

证明思路：

• 假设存在大小为 $r$ 的集合 $S = \{u_1, \ldots, u_r\}$ 被 $MC(G)$ 打散
• 对每个 $i \in [r]$，存在极大团 $K_i$ 使得 $K_i \cap S = S \backslash \{u_i\}$
• 由极大性，存在 $u'_i \in K_i \backslash S$ 使得 $u_i u'_i \notin E(G)$
• 则 $\{u_1, u'_1, \ldots, u_r, u'_r\}$ 导出 $K_r^{[2]}$ 中的某个图，矛盾

2. Sauer-Shelah引理应用

对于VC维为 $k$ 的集合系统 $\mathcal{F}$，任意大小为 $m$ 的集合 $S$ 满足： $|\mathcal{F}|_S| \leq \sum_{i=0}^{k} \binom{m}{i}$

对于本文情况，$k = r-1$，选择 $m = \lfloor\frac{9r}{c}\rfloor$，得到： $|MC(G)|_{S_m}| \leq \sum_{i=0}^{r-1} \binom{m}{i} < \frac{1}{4}c\binom{m}{r}$

3. 概率论证

反证法：假设 $ω(G) < c'n$，其中 $c' = \frac{c}{18r}$

随机选择：在 $V(G)$ 中随机选择 $S_r \subseteq S_m$，其中 $|S_r| = r$，$|S_m| = m$

概率分析：

• $S_r$ 导出团的概率至少为 $c$
• 若 $S_r$ 导出团且包含在大小 $< c'n$ 的极大团 $K$ 中，则 $S_m$ 包含 $S_r$ 但 $S_m \backslash S_r$ 不包含 $K$ 中任何顶点的概率至少为： $\frac{\binom{n-c'n}{m-r}}{\binom{n-r}{m-r}} \geq \left(\frac{n-c'n-m}{n-m}\right)^m \geq e^{-2c'm} \geq \frac{1}{4}$
• 因此存在 $S_r = S_m \cap K$ 的概率至少为 $\frac{1}{4}c$
• 期望满足条件的 $S_r$ 数量至少为 $\frac{1}{4}c\binom{m}{r}$

矛盾：这与 Sauer-Shelah 引理给出的上界矛盾。

技术创新点

1. 半导出结构的引入：$K_r^{[2]}$ 族巧妙地平衡了结构限制的强度和数量，既保证了足够的约束力，又保持了有界的禁止结构数
2. VC维的自然联系：将极大团系统的VC维与图的导出子结构直接关联，提供了新的分析视角
3. 精细的概率估计：在随机选择框架下，通过仔细的概率计算建立了团密度与团大小的定量关系
4. 参数优化：选择 $m = \lfloor\frac{9r}{c}\rfloor$ 使得 Sauer-Shelah 界和概率下界恰好产生矛盾

实验设置

本文为纯理论数学论文，不涉及实验验证。所有结果均通过严格的数学证明获得。

理论验证

• 极值例子：对于 $r=2$ 情形，论文指出导出 $K_2^{[2]}$-free图（禁止导出 $P_4$ 和 $K_{2,2}$）形成弦图的子类
• 紧性分析：虽然未给出精确的极值构造，但界的量级被证明是合理的

实验结果

主要理论结果

定理1.5（主要结果）： 设 $r ≥ 2$，$0 < c < 1$，$G$ 是包含至少 $c\binom{n}{r}$ 个 $K_r$ 副本的 $n$ 顶点图。若 $G$ 是导出 $K_r^{[2]}$-free的，则对充分大的 $n$， $ω(G) ≥ \frac{c}{18r}n$

与已有结果的比较

关键改进

1. 指数到线性：对 $c$ 的依赖从 $c^{2^{r-1}}$ 改进到 $c/r$
   • 当 $r=3$，从 $c^4$ 改进到 $c/3$
   • 当 $r=5$，从 $c^{16}$ 改进到 $c/5$
2. 有界结构数：仅需禁止 $2^{\binom{r}{2}}$ 个结构
   • $r=2$: 2个结构
   • $r=3$: 8个结构
   • $r=4$: 64个结构
3. 最优性：对于 $r=2$，本文结果与弦图界在量级上一致（都是 $Ω(cn)$），但禁止的结构更少

相关工作

经典极值图论

1. Turán定理 (1941)：确定了 $ex(n, K_k)$ 的精确值及极值图
2. Erdős-Stone-Simonovits定理 (1946, 1966)： $ex(n,H) = \left(1 - \frac{1}{χ(H)-1}\right)\binom{n}{2} + o(n^2)$
   • 对于非二部图 $H$，完全解决了渐近行为
   • 对于二部图，仅给出 $ex(n,H) = o(n^2)$

导出子图的极值理论

3. Gyárfás-Hubenko-Solymosi (2002)：
   • 导出 $K_{2,2}$-free图：$ω(G) ≥ \frac{c^2}{10}n$
   • $C_4$-free图（弦图）：$ω(G) ≥ (1-\sqrt{1-c})n$
4. Abbott-Katchalski (1979)：独立证明了弦图的紧界
5. Loh et al. (2018)：将结果推广到导出 $K_{2,t}$-free图
6. Holmsen (2020)：
   • 推广到超图和多部版本
   • 证明了抽象colorful Helly蕴含抽象fractional Helly
   • 本文直接改进了Holmsen的图论结果

VC维在图论中的应用

7. Nguyen-Scott-Seymour (2025)：建立了双导出子图密度与VC维的联系
8. Sauer (1972), Shelah (1972)：独立证明了VC维的基本界（Sauer-Shelah引理）

本文的定位

本文在Holmsen工作的基础上，通过引入半导出子结构和VC维方法，实现了定量改进。与弦图理论的联系为 $r=2$ 情形提供了自然的解释。

结论与讨论

主要结论

1. 定量改进：通过禁止 $K_r^{[2]}$ 族（至多 $2^{\binom{r}{2}}$ 个结构），将团数下界从 $Ω(c^{2^{r-1}}n)$ 改进到 $Ω(cn)$
2. 方法论贡献：建立了半导出子图与VC维的自然联系，推广了已有理论框架
3. 结构洞察：揭示了有限的结构禁止条件足以保证线性大小的团，无需像弦图那样禁止无穷多个结构

局限性

1. 常数因子：界中的常数 $\frac{1}{18r}$ 可能不是最优的，论文未讨论其紧性
2. 禁止结构数量：虽然是有界的，但 $2^{\binom{r}{2}}$ 随 $r$ 指数增长，当 $r$ 较大时仍然很多
3. 极值构造缺失：论文未提供达到下界的极值图构造
4. 渐近性质：结果要求 $n$ 充分大，具体的阈值未明确

未来方向

论文在结论部分明确提出了开放问题：

核心问题：从 $c^{2^{r-1}}$ 到 $c$ 的线性依赖的转变何时发生？更精确地说，强制关于 $c$ 的线性界所需的最小禁止结构数量是多少？

可能的研究方向：

1. 确定达到线性界的最小禁止结构族
2. 改进常数因子 $\frac{1}{18r}$
3. 构造极值例子或证明界的紧性
4. 推广到超图情形
5. 探索其他半导出结构的禁止条件

深度评价

优点

1. 重要的定量改进：
   • 将指数依赖改进为线性是实质性进展
   • 对于应用（如抽象Helly定理）具有重要意义
2. 优雅的证明技术：
   • VC维方法提供了统一的分析框架
   • 概率论证简洁有力
   • 证明完全自包含，仅依赖基本工具
3. 概念创新：
   • $K_r^{[2]}$ 族的定义巧妙平衡了约束强度和数量
   • 半导出结构的引入是自然的推广
4. 写作清晰：
   • 动机阐述充分
   • 技术细节完整
   • 与已有工作的关系明确
5. 理论深度：
   • 揭示了导出子图理论的深层结构
   • 连接了多个数学分支（极值图论、VC维理论、组合几何）

不足

1. 常数优化：
   • $\frac{1}{18r}$ 的常数可能不够精细
   • 未讨论界的紧性或提供匹配的上界构造
2. 结构数量的依赖：
   • $2^{\binom{r}{2}}$ 仍然随 $r$ 快速增长
   • 未探讨是否可以用更少的禁止结构达到类似结果
3. 具体阈值缺失：
   • "充分大的 $n$" 未量化
   • 对实际应用可能有影响
4. 推广性探讨不足：
   • 未讨论方法是否可应用于其他禁止结构
   • 与超图情形的联系仅在引言中提及
5. 开放问题的具体性：
   • 虽然提出了重要问题，但未给出猜想或部分结果

影响力评估

理论影响：

• 为导出子图极值理论提供了新工具
• VC维方法可能启发更多应用
• 对抽象Helly定理研究有直接贡献

实用价值：

• 主要是理论性质的
• 可能在算法图论和计算几何中找到应用

可复现性：

• 证明完全可验证
• 不涉及计算实验

潜在引用价值：

• 预期在极值组合学领域有较高引用
• 可能成为该方向的标准参考

适用场景

1. 理论研究：
   • 极值图论中的禁止导出子图问题
   • VC维在组合结构中的应用
   • 抽象Helly定理及其推广
2. 相关问题：
   • 其他半导出结构的研究
   • 团数与其他图参数的关系
   • 随机图中的团结构
3. 潜在应用：
   • 算法设计（利用结构性质）
   • 计算复杂性理论
   • 组合优化问题

参考文献

论文引用了以下关键文献：

1. Abbott & Katchalski (1979): 区间图的Turán型问题
2. Erdős & Simonovits (1966), Erdős & Stone (1946): ESS定理
3. Gyárfás, Hubenko & Solymosi (2002): $C_4$-free图中的大团
4. Holmsen (2020): 超图中禁止子结构的大团（本文直接改进的工作）
5. Loh et al. (2018): 导出Turán数
6. Nguyen, Scott & Seymour (2025): 导出子图密度与VC维
7. Sauer (1972), Shelah (1972): VC维的基本界
8. Turán (1941): 经典Turán定理

总体评价：这是一篇高质量的组合数学论文，在极值图论的重要问题上取得了实质性进展。通过引入半导出结构和VC维方法，作者成功地将Holmsen的指数界改进为线性界，同时保持了禁止结构数量的有界性。证明技术优雅且富有洞察力，为该领域提供了新的研究工具和方向。论文的主要贡献在于理论层面，但其方法和思想可能对相关领域产生广泛影响。