Tel-Aviv University
School of Mathematical Sciences

Department Colloquium

Monday, December 3, 2012

Schreiber 006, 12:15

Wojciech Samotij

University of Cambridge and Tel Aviv University

Independent sets in hypergraphs

Many important theorems and conjectures in combinatorics, such as the theorem
of Szemeredi on arithmetic progressions and the Erdos-Stone Theorem 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 extremal and probabilistic combinatorics 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 approaches solved very similar
sets of longstanding open problems, the methods used are very different from one another and
have different strengths and weaknesses.

In the talk, we describe a third, completely different 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 by
showing that every independent set is almost contained in one of a small number of relatively
sparse sets. We then show how to derive many interesting results as fairly straightforward
consequences of this abstract theorem.

Based on joint work with Jozsef Balogh and Robert Morris.

Coffee will be served at 12:00 before the lecture
at Schreiber building 006