Combinatorial theorems in sparse random sets

Abstract

We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Turán's theorem, Szemerédi's theorem and Ramsey's theorem, hold almost surely inside sparse random sets. For instance, we extend Turán's theorem to the random setting by showing that for every $\epsilon >0$ and every positive integer $t\ge 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án 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ödl and Schacht.

69 pages

References in corpus (1)

• Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs

Cited by in corpus (7)

• Further applications of the Container Method
• A relative Szemerédi theorem
• Mantel's Theorem for random graphs
• Four variants of the Fourier-analytic transference principle
• Turán's Theorem for random graphs
• Dirac's theorem for random graphs
• Additive combinatorics with a view towards computer science and cryptography: An exposition