Combinatorial theorems in sparse random sets

David Conlon

doi:10.4007/annals.2016.184.2.2

Combinatorial theorems in sparse random sets

2016-09-01

91

OA

AI

DOI：10.4007/annals.2016.184.2.2

Original

Original request for help

Save

Abstract

En 中文

We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Turan's theorem, Szemeredi's theorem and Ramsey's theorem, hold almost surely inside sparse random sets. For instance, we extend Turan's theorem to the random setting by showing that for every epsilon > 0 and every positive integer t >= 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 Cn(-2/(t+ 1)), then, with probability tending to 1 as n tends to infinity, every subgraph of G with at least (1 - 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 Turan 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, Rodl and Schacht.

Keywords:

RANDOM DISCRETE STRUCTURES

K-UNIFORM HYPERGRAPHS

TURANS EXTREMAL PROBLEM

RANDOM GRAPHS

RAMSEY PROPERTIES

ARITHMETIC PROGRESSIONS

3-UNIFORM HYPERGRAPHS

K-4-FREE SUBGRAPHS

RANDOM SUBSETS

UPPER TAILS

Combinatorial theorems in sparse random sets

Abstract

Journal

Organization