Title: Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions Show Chinese title

Title: 哈密顿循环在伪随机图中的鲁棒性与近似分解

Abstract: Dirac's classical theorem asserts that, for $n \ge 3$, any $n$-vertex graph with minimum degree at least $n/2$ is Hamiltonian. Furthermore, if we additionally assume that such graphs are regular, then, by the breakthrough work of Csaba, K\"uhn, Lo, Osthus and Treglown, they admit a decomposition into Hamilton cycles and at most one perfect matching, solving the well-known Nash-Williams conjecture. In the pseudorandom setting, it has long been conjectured that similar results hold in much sparser graphs. We prove two overarching theorems for graphs that exclude excessively dense subgraphs, which yield asymptotically optimal resilience and Hamilton-decomposition results in sparse pseudorandom graphs. In particular, our results imply that for every fixed $\gamma > 0$, there exists a constant $C > 0$ such that if $G$ is a spanning subgraph of an $(n,d,\lambda)$-graph satisfying $\delta(G) \ge (\tfrac12 + \gamma)d$ and $d/\lambda \ge C$, then $G$ must contain a Hamilton cycle. Secondly, we show that for every $\varepsilon > 0$, there is $C > 0$ so that every $(n,d,\lambda)$-graph with $d/\lambda \ge C$ contains at least $(\tfrac12 - \varepsilon)d$ edge-disjoint Hamilton cycles, and, finally, we prove that the entire edge set of $G$ can be covered by no more than $(\tfrac12 + \varepsilon)d$ such cycles. All bounds are asymptotically optimal and significantly improve earlier results on Hamiltonian resilience, packing, and covering in sparse pseudorandom graphs. Show Chinese abstract

Abstract: 狄拉克的经典定理指出，对于$n \ge 3$，任何具有最小度数至少为$n/2$的$n$顶点图都是哈密顿图。 此外，如果我们进一步假设这些图是正则的，那么根据Csaba、Kühn、Lo、Osthus和Treglown的突破性工作，它们可以分解为哈密顿环和至多一个完美匹配，从而解决了著名的纳什-威廉姆斯猜想。 在伪随机设置中，长期以来人们一直猜测在更稀疏的图中也会出现类似的结果。 我们证明了两个总体定理，这些定理适用于排除过于密集子图的图，这在稀疏伪随机图中产生了渐近最优的鲁棒性和哈密顿分解结果。 特别是，我们的结果表明，对于每个固定的$\gamma > 0$，存在一个常数$C > 0$，使得如果$G$是一个$(n,d,\lambda)$-图的支撑子图，满足$\delta(G) \ge (\tfrac12 + \gamma)d$和$d/\lambda \ge C$，则$G$必须包含一个哈密顿循环。 其次，我们证明对于每个 $\varepsilon > 0$，存在 $C > 0$使得每个具有 $d/\lambda \ge C$ 的 $(n,d,\lambda)$-图至少包含 $(\tfrac12 - \varepsilon)d$个边不相交的哈密顿环，并且最后，我们证明 $G$ 的整个边集可以被不超过 $(\tfrac12 + \varepsilon)d$个这样的环覆盖。 所有界限都是渐近最优的，并显著改进了在稀疏伪随机图中关于哈密顿鲁棒性、匹配和覆盖的先前结果。