Combinatorial theorems in sparse random sets
Combinatorial theorems in sparse random sets
复制标题
稀疏随机集中的组合定理
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
W. Gowers
中科院分区：
文献类型：
--
作者：
D. Conlon;W. Gowers
我们开发了一种新的技术，使我们能够以统一的方式表明，许多著名的组合定理，包括Tur\'an定理，Szemer\' edi定理和Ramsey定理，几乎肯定在稀疏随机集内。例如，我们将Tur\'an定理推广到随机情形，证明了对于任意0和任意正整数t\geq 3，存在一个常数C，使得如果G是n个顶点的随机图，其中每条边的独立选择概率至少为Cn ^{-2/（t +1）}，则当n趋于无穷大时，G的每个至少有（1-\frac {1}{t-1}+\frac {1}{t-1}）e（G）$边的子图都包含K_t $的一个拷贝.这是急剧上升到常数$C $。我们还展示了如何证明结构结果的稀疏类似物，给出了两个主要的应用，上述随机Tur\'an定理的稳定版本和稀疏超图删除引理。沙赫特以及弗里德古特、R 'odl和沙赫特最近以不同的方式独立获得了许多类似的结果。
We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Tur\'an's theorem, Szemer\'edi's theorem and Ramsey's theorem, hold almost surely inside sparse random sets. For instance, we extend Tur\'an's theorem to the random setting by showing that for every $\epsilon > 0$ and every positive integer $t \geq 3$ there exists a constant $C$ such that, if $G$ is a random graph on $n$ vertices where each edge is chosen independently with probability at least $C n^{-2/(t+1)}$, then, with probability tending to $1$ as $n$ tends to infinity, every subgraph of $G$ with at least $(1 - \frac{1}{t-1} + \epsilon) e(G)$ edges contains a copy of $K_t$. This is sharp up to the constant $C$. We also show how to prove sparse analogues of structural results, giving two main applications, a stability version of the random Tur\'an theorem stated above and a sparse hypergraph removal lemma. Many similar results have recently been obtained independently in a different way by Schacht and by Friedgut, R\"odl and Schacht.