On the KŁR conjecture in random graphs
On the KŁR conjecture in random graphs
复制标题
关于随机图中的 KÅR 猜想
DOI：
10.1007/s11856-014-1120-1
复制
发表时间：
2014
影响因子：
1
通讯作者：
M. Schacht
中科院分区：
文献类型：
--
作者：
D. Conlon;W. T. Gowers;W. Samotij;M. Schacht
KŁR猜想是Kohayakawa，Łuczak和Rödl提出的一个命题，证明了当p=p(N)时，随机图Gn，p的几乎必然的所有子图都满足嵌入引理，从而补充了Kohayakawa和Rödl的稀疏正则引理.我们证明了这一猜想的一个变种，该猜想对于大多数已知的随机图的应用是足够的。特别地，由于Conlon，Gowers和Schacht，我们的结果暗示了经典极值组合定理的一些最近的概率版本。我们还讨论了几个进一步的应用。
The KŁR conjecture of Kohayakawa, Łuczak, and Rödl is a statement that allows one to prove that asymptotically almost surely all subgraphs of the random graphGn,p, for sufficiently largep:=p(n), satisfy an embedding lemma which complements the sparse regularity lemma of Kohayakawa and Rödl. We prove a variant of this conjecture which is sufficient for most known applications to random graphs. In particular, our result implies a number of recent probabilistic versions, due to Conlon, Gowers, and Schacht, of classical extremal combinatorial theorems. We also discuss several further applications.
登录
查看更多内容
矩阵和稀疏图的 Szemerédi 正则引理
DOI：
10.1017/s0963548310000490
发表时间：
2010
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
A. Scott
通讯作者：
A. Scott
影响因子：
0.8
作者：
Guoping Jin
通讯作者：
Guoping Jin
随机离散结构的拉姆齐性质
影响因子：
1
作者：
E. Friedgut;V. Rödl;M. Schacht
通讯作者：
M. Schacht
随机离散结构的稳定性结果
DOI：
--
发表时间：
2011
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
Wojciech Samotij
通讯作者：
Wojciech Samotij
稀疏随机图中的正则对 I
DOI：
--
发表时间：
2003
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
Y. Kohayakawa;V. Rödl
通讯作者：
V. Rödl