Combinatorial theorems in sparse random sets

By David Conlon, William T. Gowers. 2010

243 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/6c3ce3d0c037214378b2d4c35173cdd1cb5b4dba

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, methodology): “The theory was first developed independently in different ways by Rödl et al. [148, 163, 162] and Gowers [89].”
On the KŁR conjecture in random graphs (2013, background): “In this context, this can be traced back to the work of Rödl and Ruciński in [72].”
The existence of designs via iterative absorption (2016, background): “Recent highlights include the transference results for random hypergraphs by Conlon and Gowers [10] as well as Schacht [39].”
The chromatic thresholds of graphs (2011, background): “example, the recent breakthroughs of Conlon and Gowers [10] and Schacht [36]).”