Almost‐spanning universality in random graphs
Almost‐spanning universality in random graphs
复制标题
随机图中几乎跨越的普遍性
DOI：
10.1002/rsa.20661
复制
发表时间：
2015
影响因子：
1
通讯作者：
N. Skoric
中科院分区：
文献类型：
--
作者：
D. Conlon;Asaf Ferber;R. Nenadov;N. Skoric
如果一个图G包含最多n个顶点上的每个图，且最大度数不超过Δ，则称其为h （n，Δ）‐全称。已知对于任意ε>和任意自然数Δ，存在c>，使得随机图G（n, p）渐近几乎肯定是h（(1−ε)n，Δ）‐通的，对于p≥c(logn/n)1/Δ。绕过这个自然边界，我们证明了对于Δ≥3，当p≠n−1Δ−1log5n时，同样的结论成立。©2016 Wiley期刊公司随机结构。Alg。生态学报，50,380-393,2017
A graph G is said to be ℋ(n,Δ) ‐universal if it contains every graph on at most n vertices with maximum degree at most Δ. It is known that for any ε>0 and any natural number Δ there exists c>0 such that the random graph G(n, p) is asymptotically almost surely ℋ((1−ε)n,Δ) ‐universal for p≥c(logn/n)1/Δ . Bypassing this natural boundary, we show that for Δ≥3 the same conclusion holds when p≫n−1Δ−1log5n . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 380–393, 2017
对抗性边缘去除后几乎跨越随机图的子图
DOI：
10.1017/s0963548313000199
发表时间：
2013
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
J. Böttcher;Y. Kohayakawa;A. Taraz
通讯作者：
A. Taraz