Combinatorial theorems in sparse random sets

Details Combinatorial theorems in sparse random sets Combinatorial theorems in sparse random sets

2010-11-18

arxiv.org/abs/1011.4310v1

Mathematics

Combinatorics

70 pages

Scientific paper

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 >= 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.

Affiliated with

Also associated with

No associations

Rating

Combinatorial theorems in sparse random sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorial theorems in sparse random sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial theorems in sparse random sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-116586