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.