Spanning universality in random graphs
Spanning universality in random graphs
复制标题
跨越随机图中的普遍性
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Nenadov
中科院分区：
文献类型：
--
作者：
Asaf Ferber;R. Nenadov
如果一个图包含具有 n 个顶点且最大度至多为 Δ 的每个图作为子图，则该图被称为 H(n,Δ) 是通用的。 Dellamonica、Kohayakawa、Rödl 和 Ruciński 使用 Alon 和 Füredi 引入的“基于匹配”的嵌入技术来表明，随机图 Gn,p 几乎肯定是渐进的 H(n,Δ) ‐ 对于 p=Ω((logn/n)1/Δ) 是通用的，这是 Δ 顶点的每个子集都有一个公共属性的阈值 邻居。这个界限已经成为该领域的基准，并且在随机图中嵌入最大度 Δ 的跨越图的许多后续结果仅被证明达到这个阈值。我们通过证明 Gn,p 几乎肯定是 H(n,Δ) ——对于 p=Ω(n−1/(Δ−0.5)log3n) 来说是通用的，朝着克服以前技术的局限性迈出了一步。
A graph is said to be H(n,Δ) ‐universal if it contains every graph with n vertices and maximum degree at most Δ as a subgraph. Dellamonica, Kohayakawa, Rödl and Ruciński used a “matching‐based” embedding technique introduced by Alon and Füredi to show that the random graph Gn,p is asymptotically almost surely H(n,Δ) ‐universal for p=Ω((logn/n)1/Δ) , a threshold for the property that every subset of Δ vertices has a common neighbor. This bound has become a benchmark in the field and many subsequent results on embedding spanning graphs of maximum degree Δ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing that Gn,p is almost surely H(n,Δ) ‐universal for p=Ω(n−1/(Δ−0.5)log3n) .
对抗性边缘去除后几乎跨越随机图的子图
DOI：
10.1017/s0963548313000199
发表时间：
2013
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
J. Böttcher;Y. Kohayakawa;A. Taraz
通讯作者：
A. Taraz