FoCM 2014 conference

Workshop A4 - Graph Theory and Combinatorics - Semi-plenary talk

December 13, 17:05 ~ 17:55 - Room B11

Extremal combinatorics in random discrete structures

Mathias Schacht

Universität Hamburg, Germany   -

We survey on recent results at the intersection of extremal combinatorics and random graph theory. More precisely, we consider thresholds for extremal properties of random discrete structures. Among other problems, we shall discuss the threshold for Szemerédi's theorem on arithmetic progressions in random subsets of the integers and the threshold for Turán-type problems for random graphs and hypergraphs, which were obtained independently by Conlon and Gowers and by the speaker. Furthermore, we discuss recent general results on independent sets in hypergraphs by Balogh, Morris and Samotij and by Thomason and Saxton, which led to new proofs of these results and have already had many other applications in the area.

View abstract PDF