Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
复制标题
随机扰动图中的有界度生成树
DOI：
10.1137/15m1032910
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Michael Krivelevich;Matthew Kwan;B. Sudakov
我们证明了对于任意固定稠密图G和相同顶点数的有界度树T，G的适度随机扰动通常包含T的一个副本。这结合了嵌入树到固定稠密图和随机图的研究问题的观点，并扩展了现有的随机扰动图的研究相当大的机构。具体地说，我们证明了存在$c = c（\alpha，\Delta）$使得如果G是一个最小度至少为$\alpha n$的n-顶点图，T是一个最大度至多为$\Delta$的n-顶点树，那么如果我们给G加上cn条一致随机边，所得到的图将几乎必然渐近地包含T（如$n\to\infty$）.我们的证明使用了一个引理，关于一个稠密图分解成超正则对可比的大小，这可能是独立的利益。
We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy of T . This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizeable body of existing research on randomly perturbed graphs. Specifically, we show that there is $c = c(\alpha,\Delta)$ such that if G is an n-vertex graph with minimum degree at least $\alpha n$, and T is an n-vertex tree with maximum degree at most $\Delta$ , then if we add cn uniformly random edges to G, the resulting graph will contain T asymptotically almost surely (as $n\to\infty$ ). Our proof uses a lemma concerning the decomposition of a dense graph into super-regular pairs of comparable sizes, which may be of independent interest.