Tel Aviv University
The next colloquium talk will be held on:
Monday, 3/12/2012, 12:15, Schreiber 006, Tel Aviv University.
Speaker: Wojciech Samotij (University of Cambridge and Tel Aviv University)
Title: Independent sets in hypergraphs.
The abstract is given below. Tea and coffee at 12:00, same room.
Hope to see you there. For information about future colloquia, see
Abstract: 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
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.
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel <firstname.lastname@example.org>
Announcement from: <email@example.com>