2025-11-23T15:40:17.357223

Lollipops, dense cycles and chords

DvoÅÃ¡k, Martins, ThomassÃ© et al.

In 1980, Gupta, Kahn and Robertson proved that every graph $G$ with minimum degree at least $k\geq 2$ contains a cycle $C$ containing at least $k+1$ vertices each having at least $k$ neighbors in $C$ (so $C$ has at least $\frac{(k+1)(k-2)}{2}$ chords). In this work, we go further by showing that some of its edges can be contracted to obtain a graph with high minimum degree (we call such a minor of $C$ a \emph{cyclic minor}). We then investigate further cycles having cliques as cyclic minors, and show that minimum degree at least $O(k^2)$ guarantees a cyclic $K_k$-minor.

academic

Lollipops, dense cycles and chords

基本信息

论文ID: 2502.04726
标题: Lollipops, dense cycles and chords
作者: Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé, Nicolas Trotignon
分类: math.CO (组合数学)
发表时间: 2025年10月13日
论文链接: https://arxiv.org/abs/2502.04726

摘要

1980年，Gupta, Kahn和Robertson证明了每个最小度至少为 $k \geq 2$ 的图 $G$ 都包含一个循环 $C$ ，该循环包含至少 $k+1$ 个顶点，每个顶点在 $C$ 中都有至少 $k$ 个邻居（因此 $C$ 至少有 $\frac{(k+1)(k-2)}{2}$ 条弦）。本文进一步证明了可以通过收缩某些边来获得具有高最小度的图（称为循环minor）。随后研究了具有团作为循环minor的循环，并证明最小度至少为 $O(k^2)$ 可以保证存在循环 $K_k$ -minor。

研究背景与动机

问题背景

经典问题的延续：图论中的一个经典问题是研究最小度与图的稠密子结构之间的关系。许多定理表明，图中足够高的最小度可以保证存在某种稠密、复杂或连通性良好的子结构。
已有结果的局限性：Gupta-Kahn-Robertson定理虽然保证了具有许多弦的循环的存在，但没有进一步研究这些循环的结构性质，特别是通过边收缩操作能够获得什么样的稠密结构。
Lollipop方法的应用：Lollipop方法自Thomason在1978年首次提出以来，主要用于证明哈密顿循环的存在性，本文将其推广用于构造稠密的收缩循环。

研究动机

本文的核心动机是将经典的GKR定理从简单的弦计数扩展到结构性分析，通过引入"循环minor"的概念，研究如何通过边收缩操作从稠密循环中获得更加稠密的图结构。

核心贡献

扩展GKR定理：不仅证明了稠密循环的存在，还证明了可以通过收缩操作获得具有高最小度或高平均度的图。
引入循环minor概念：定义了循环minor的概念，即从图的哈密顿子图通过收缩哈密顿循环的某些边得到的图。
建立度数与循环minor的关系：证明了 $f(\ell) = O(\ell^2)$ ，其中 $f(\ell)$ 是保证存在 $K_\ell$ 作为循环minor的最小度数下界。
提供算法框架：给出了多项式时间算法来构造满足定理条件的循环和相应的边收缩集合。

方法详解

任务定义

给定最小度为 $k$ 的图 $G$ ，构造一个循环 $C$ 及其边子集 $X_1, X_2$ ，使得通过收缩 $X_i$ 中的边可以获得具有高最小度或高平均度的图。

核心概念

Lollipop结构

定义：图 $G$ 中的lollipop $L$ 是一对 $(P,C)$ ，其中：

$P = p_1...p_s$ 是路径
$C = c_1...c_tc_1$ 是循环
$p_s = c_1$ 且 $V(P) \cap V(C) = \{c_1\}$

最优性：Lollipop $L = (P,C)$ 是最优的当且仅当：

$L$ 是顶点包含意义下极大的
在所有定义在 $V(L)$ 上的lollipop中， $L$ 的循环长度最大

活跃路径系统

通过递归定义构造活跃路径集合 $S_1, S_2, ...$ ：

$S_1 = \{c_1c_2...c_t, c_1c_tc_{t-1}...c_2\}$
对于 $i \geq 1$ ，从 $S_i$ 构造 $S_{i+1}$ ：对于 $Q = c_1...u \in S_i$ 和弦 $uv$ ，如果 $vw$ 是 $C$ 的边（ $w$ 是 $v$ 在 $vQu$ 中的邻居），则将路径 $c_1QvuQw$ 加入 $S_{i+1}$

主要定理

定理1.1（主要结果）

如果 $G$ 的最小度至少为 $k \geq 2$ ，则 $G$ 包含一个循环 $C$ ，满足：

$C$ 包含至少 $k+1$ 个顶点，每个都在 $C$ 中有至少 $k$ 个邻居
存在 $X_1, X_2 \subseteq E(C)$ $X_{1}, X_{2} \subseteq E (C)$ 使得：
- 收缩 $X_1$ 中的边得到最小度至少为 $\lceil\frac{k+2}{2}\rceil$ 的图
- 收缩 $X_2$ 中的边得到平均度至少为 $\frac{2}{3}(k+1)$ 的图

技术创新点

精细化分析：不仅计算弦的数量，还分析弦的分布模式，确保存在足够多的"交叉弦"以支持有效的边收缩。
活跃顶点理论：通过活跃路径的概念，系统地识别具有高度数的顶点，并分析它们在收缩操作中的行为。
Marcus-Tardos定理的应用：利用该定理将具有高平均度的循环minor进一步收缩为大的完全二部图。

实验设置

理论验证

本文主要是理论性工作，通过严格的数学证明验证结果：

小规模验证：
- $f(3) = 2$ , $f(4) = 3$ , $6 \leq f(5) \leq 8$
- 通过具体构造验证了小团的循环minor存在性
极值例子：
- 完全图 $K_t$ 作为紧性例子，说明某些结论是最优的
- 冰面体（icosahedron）说明 $f(5) \geq 6$