论文标题
在随机扰动图中的三角形
Triangles in randomly perturbed graphs
论文作者
论文摘要
我们研究了在随机扰动的图形模型中找到成对的顶点 - 二合一三角形的问题，该图是满足给定最低度条件的任何$ n $ vertex Graph $ g $和二项式随机图$ g（n，p）$的结合。我们证明，几乎可以肯定的是$ g \ cup g（n，p）$至少包含$ \ min \ {δ（g），\ lfloor n/3 \ rfloor \} $ pairwisex-disex-disexingles，提供了$ p \ ge c \ ge c \ log n/n $，其中$ c $是一个大的常数。这是Dirac旧结果的扰动版本。 我们的结果在渐近上是最佳的，并回答了Han，Morris和Treglown的问题[RSA，2021年，第1期。 3，480--516]以强烈的形式。我们还证明了我们的结果的稳定性版本，在成对顶点 - 偶口三角形的情况下，这扩展了Han，Morris和Treglown的结果[RSA，2021年，否。 3，480--516]。以及Balogh，Treglown和Wagner的结果[CPC，2019年，第1期。 2，159--176]这完全解决了随机扰动图中三角因子的存在。 我们认为，本文介绍的方法对于各种相关问题很有用：我们讨论了对集团因素，周期因素和$ 2美元的概括。
We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$-vertex graph $G$ satisfying a given minimum degree condition and the binomial random graph $G(n,p)$. We prove that asymptotically almost surely $G \cup G(n,p)$ contains at least $\min\{δ(G), \lfloor n/3 \rfloor\}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$, where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac. Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, 2021, no. 3, 480--516] in a strong form. We also prove a stability version of our result, which in the case of pairwise vertex-disjoint triangles extends a result of Han, Morris, and Treglown [RSA, 2021, no. 3, 480--516]. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159--176] this fully resolves the existence of triangle factors in randomly perturbed graphs. We believe that the methods introduced in this paper are useful for a variety of related problems: we discuss possible generalisations to clique factors, cycle factors, and $2$-universality.
