论文标题
强大的corrádi-hajnal定理
A robust Corrádi--Hajnal Theorem
论文作者
论文摘要
对于[0,1] $中的图形$ g $和$ p \，我们用$ g_p $表示通过独立保持$ g $的每个边缘获得的$ g $的随机稀疏，并带有概率$ p $。我们表明存在$ c> 0 $，这样，如果$ p \ geq c（\ log n）^{1/3} n^{ - 2/3} $，$ g $是$ n $ -vertex图形，$ n $ n \ in 3 \ mathbb {n}包含一个三角因子。最低度条件和概率状况（直到$ c $的选择）都很紧。我们的结果可以看作是Corrádi和Hajnal的开创性定理的普遍加强，该定理涉及包含三角因素的极端最低度条件（我们的结果中对应于$ p = 1 $），以及Johansson，Kahn和Vu，与$ G（$ G（N，p）相关的threshold涉及$ g（n，p）$ g（n，p）的出现。这也意味着对最小程度至少$ \ tfrac {2n} {3} $的图表中的三角因子数量的下限。
For a graph $G$ and $p\in[0,1]$, we denote by $G_p$ the random sparsification of $G$ obtained by keeping each edge of $G$ independently, with probability $p$. We show that there exists a $C>0$ such that if $p\geq C(\log n)^{1/3}n^{-2/3}$ and $G$ is an $n$-vertex graph with $n\in 3\mathbb{N}$ and $δ(G)\geq \tfrac{2n}{3}$, then with high probability $G_p$ contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of $C$, are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corrádi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to $p=1$ in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in $G(n,p)$ (corresponding to $G=K_n$ in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least $\tfrac{2n}{3}$ which gets close to the truth.
