Department of

December 2013 January 2014 February 2014 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 1 2 3 4 1 8 9 10 11 12 13 14 5 6 7 8 9 10 11 2 3 4 5 6 7 8 15 16 17 18 19 20 21 12 13 14 15 16 17 18 9 10 11 12 13 14 15 22 23 24 25 26 27 28 19 20 21 22 23 24 25 16 17 18 19 20 21 22 29 30 31 26 27 28 29 30 31 23 24 25 26 27 28

Tuesday, January 21, 2014

**Abstract:** Many important theorems and conjectures in combinatorics, such as the theorem of Szemeredi on arithmetic progressions and the Erdos-Stone The- orem in extremal graph theory, can be phrased as statements about families of independent sets in certain uniform hypergraphs. In recent years, an important trend in the area has been to extend such classical results to the so-called `sparse random setting'. This line of research has recently culminated in the breakthroughs of Conlon and Gowers and of Schacht, who developed general tools for solving problems of this type. Although these two papers solved very similar sets of longstanding open problems, the meth- ods used are very diferent from one another and have diferent strengths and weaknesses. In this talk, we explain a third, completely diferent approach to proving extremal and structural results in sparse random sets that also yields their natural `counting' counterparts. We give a structural characterization of the independent sets in a large class of uniform hypergraphs. In this talk we focus on a specic application of the method, proving the following theorem: For every r we determine the best possible mr(n) that for every $c > 0$ for $m > mr(n)$ almost all $K_{r+1}$-free $n$-vertex graphs with $m$ edges are $r$-partite. Joint work with Robert Morris, Wojciech Samotij and Lutz Warnke.