Blow-up lemmas for sparse graphs
Blow-up lemmas for sparse graphs
复制标题
稀疏图的爆炸引理
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Y. Person
中科院分区：
文献类型：
--
作者：
Peter Allen;Julia Bottcher;Hiêp Hàn;Y. Kohayakawa;Y. Person
爆破引理指出，一个超正则对系统包含所有有界度生成图作为子图嵌入到一个相应的完全对系统中。这个引理在极值组合学中有着深远的应用。
我们证明稀疏类似物的爆破引理的子图的随机和伪随机图。我们的主要结果是爆破引理的三个稀疏形式：一个是在G（n，p）$的子图中嵌入最大度为$Delta$的支撑图，其中$p=C（log n/n）^{1/Delta}$;一个是在G（n，p）$的子图中嵌入最大度为$Delta$且退化度为$D$的支撑图，其中$p=C_DeltaIG（log n/nIG）^{1/（2D+1）}$，以及在$（p，cp^{max（4，（3Delta+1）/2）}n）$-双混杂图中嵌入最大度为$Delta$的生成图的问题。
我们也考虑这些引理的各种应用。
The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has far-reaching applications in extremal combinatorics.
We prove sparse analogues of the blow-up lemma for subgraphs of random and of pseudorandom graphs. Our main results are the following three sparse versions of the blow-up lemma: one for embedding spanning graphs with maximum degree $Delta$ in subgraphs of $G(n,p)$ with $p=C(log n/n)^{1/Delta}$; one for embedding spanning graphs with maximum degree $Delta$ and degeneracy $D$ in subgraphs of $G(n,p)$ with $p=C_Deltaig(log n/nig)^{1/(2D+1)}$; and one for embedding spanning graphs with maximum degree $Delta$ in $(p,cp^{max(4,(3Delta+1)/2)}n)$-bijumbled graphs.
We also consider various applications of these lemmas.
登录
查看更多内容
影响因子：
1.1
作者：
Peter Allen;Julia Böttcher;Hiêp Hàn;Y. Kohayakawa;Y. Person
通讯作者：
Peter Allen;Julia Böttcher;Hiêp Hàn;Y. Kohayakawa;Y. Person
关于随机图中的 KÅR 猜想
影响因子：
1
作者：
D. Conlon;W. T. Gowers;W. Samotij;M. Schacht
通讯作者：
M. Schacht
对抗性边缘去除后几乎跨越随机图的子图
DOI：
10.1017/s0963548313000199
发表时间：
2013
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
J. Böttcher;Y. Kohayakawa;A. Taraz
通讯作者：
A. Taraz
DOI：
10.1137/13093827x
发表时间：
--
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
J. Böttcher;Y. Kohayakawa;A. Taraz;A. Würfl
通讯作者：
A. Würfl
密集随机图中的色阈值
影响因子：
1
作者：
Allen P
通讯作者：
Allen P