2-universality in Randomly Perturbed Graphs
2-universality in Randomly Perturbed Graphs
复制标题
2-随机扰动图中的普遍性
DOI：
10.1016/j.ejc.2020.103118
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Olaf Parczyk
中科院分区：
文献类型：
--
作者：
Olaf Parczyk
一个图G称为图族F的泛图，如果它包含每个元素F∈ F作为一个子图。设F（n，2）是所有最大度为2的图的族. Ferber等人（2019）证明了存在一个C使得对于p≥ C（n− 2 scin 3 log 1 scin 3 n），随机图G（n，p）aas是F（n，2）-泛的，这是渐近最优的。对任意最小度δ（G α）≥ α n的n-顶点图G α，艾格纳和Brandt（1993）证明了：当α≥ 2 scin 3时，G α是F（n，2）-泛的（这是最优的）。本文考虑随机扰动图的模型，即并G α <$G（n，p）.证明了aas G α <$G（n，p）是F（n，2）-泛的，只要α∈（0，1）且p= ω（n− 2 scin 3）.这是渐进最优的，并且在相应参数中改进了上述两个结果。此外，这扩展了Böttcher等人的结果。(in press），他们在这些值处嵌入给定的F∈ F（n，2）。我们还证明了族F（n，2）的具有普适性的变体，即F（n，2）中围长至少为1/2的所有图.例如，存在一个只依赖于α的ε 0，使得对于所有ε ≥ ε 0，p= ω（1 scinn）对于F ε（n，2）-普适性已经是足够的。
A graph G is called universal for a family of graphs F if it contains every element F∈ F as a subgraph. Let F (n, 2) be the family of all graphs with maximum degree 2. Ferber et al.(2019) proved that there exists a C such that for p≥ C (n− 2∕ 3 log 1∕ 3 n) the random graph G (n, p) aas is F (n, 2)-universal, which is asymptotically optimal. For any n-vertex graph G α with minimum degree δ (G α)≥ α n Aigner and Brandt (1993) proved that G α is F (n, 2)-universal if α≥ 2∕ 3 (and this is optimal). In this note, we consider the model of randomly perturbed graphs, which is the union G α∪ G (n, p). We prove that aas G α∪ G (n, p) is F (n, 2)-universal provided that α∈(0, 1) and p= ω (n− 2∕ 3). This is asymptotically optimal and improves on both results from above in the respective parameter. Furthermore, this extends a result of Böttcher et al.(in press), who embed a given F∈ F (n, 2) at these values. We also prove variants with universality for the family F ℓ (n, 2), all graphs from F (n, 2) with girth at least ℓ. For example, there exists an ℓ 0 depending only on α such that for all ℓ≥ ℓ 0 already p= ω (1∕ n) is sufficient for F ℓ (n, 2)-universality.
登录
查看更多内容
随机扰动超图中的哈密顿性
DOI：
10.1016/j.jctb.2019.12.005
发表时间：
2020
期刊：
Series B
影响因子：
--
作者：
Han, Jie;Zhao, Yi
通讯作者：
Zhao, Yi
随机扰动图的拉姆齐性质：派系和循环
DOI：
10.1017/s0963548320000231
发表时间：
2020
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
Das S
通讯作者：
Das S
影响因子：
1
作者：
Böttcher J
通讯作者：
Böttcher J
随机扰动密集图中的平铺
DOI：
10.1017/s0963548318000366
发表时间：
2018
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
BALOGH J
通讯作者：
BALOGH J
随机扰动图中的生成树
影响因子：
1
作者：
F. Joos;J. Kim
通讯作者：
J. Kim