作者： Tınaz Ekim, Burak Nur Erdem, John Gimbel
主题分类： Combinatorics (math.CO); Discrete Mathematics (cs.DM)
MSC 分类： 05C30, 05C35, 05C55
一个顶点集合称为 $k$-稀疏集，如果它诱导的子图的最大度数不超过 $k$。本文研究固定阶数的无三角形图中最大 $k$-稀疏集的大小。
主要结果示例：
- 每个 11 阶的无三角形图都包含一个 1-稀疏的 5 顶点集；
- 每个 13 阶的无三角形图都包含一个 2-稀疏的 7 顶点集；
- 每个 8 阶的无三角形图都包含一个 3-稀疏的 6 顶点集。
上述结果均为最优的（即存在达到该界的极图）。
对于固定的 $k$，本文还研究了 $n$ 阶无三角形图中最大 $k$-稀疏集大小的增长速率。此外，考虑了如下类型的 Ramsey 数：给定 $i$，最小的 $n$ 是多少，使得所有 $n$ 阶的无三角形图要么包含一个 4-圈，要么包含一个大小为 $i$ 的 $k$-稀疏集。
作者结合直接证明技巧和高效的图枚举算法，获得了缺陷 Ramsey 数以及与无三角形图中最大稀疏集相关参数的若干数值，同时给出了对应的极图。