Combinatorics Seminar
When: Sunday, January 13, 10am
Where: Schreiber 309
Speaker: Ehud Friedgut, Weizmann Institute
Title: A sharp threshold for van der Waerden properties
of random sets of integers
Abstract:
van der Waerden's theorem tells us that for any r and k there
exists n such that for any r-coloring of the integers {1,2,...,n}
there exists a monochromatic k-term arithmetic progression.
Rodl and Rucinski showed that for any r and k there exist
constants c and C, such that a random subset of {1,2,...,n} of size
cn^{(k-2)/(k-1)} has this property with probability that tends to 0
as n tends to infinity, and a random subset of size Cn^{(k-2)/(k-1)}
has this property with probability that tends to 1.
We show (at least for the case of 2 colors) that this can be
sharpened, and that there exists t(n), so that for any epsilon>0,
c and C can be replaced by (1-epsilon)t(n) and (1+epsilon)t(n).
Our main tool is a theorem of Bourgain, which characterizes
non-sharp thresholds. An additional tool, that turns out to be
crucial in the proof, is a recent powerful theorem of
Balogh-Morris-Samotij which offers a better understanding of
the independent sets in hypergraphs.
The talk will be self contained.
Joint work with Hiep Han, Yury Person and Mathias Schacht.