Independent sets in hypergraphs

Add to your list(s) Download to your calendar using vCal

• Wojciech Samotij (University of Cambridge)
• Thursday 27 October 2011, 14:30-15:30
• MR12.

If you have a question about this talk, please contact Andrew Thomason.

We say that a hypergraph is stable if each sufficiently large subset of its vertices either spans many hyperedges or is very structured. Hypergraphs that arise naturally in many classical settings possess the above property. For example, the famous stability theorem of Erdős and Simonovits and the triangle removal lemma of Ruzsa and Szemerédi imply that the hypergraph on the vertex set $E(K_n)$ whose hyperedges are the edge sets of all triangles in $K_n$ is stable. In the talk, we will present the following general theorem: If $(H_n)_n$ is a sequence of stable hypergraphs satisfying certain technical conditions, then a typical (i.e., uniform random) $m$-element independent set of $H_n$ is very structured, provided that $m$ is sufficiently large. The above abstract theorem has many interesting corollaries, some of which we will discuss. Among other things, it implies sharp bounds on the number of sum-free sets in a large class of finite Abelian groups and gives an alternate proof of Szemerédi’s theorem on arithmetic progressions in random subsets of integers.

Joint work with Noga Alon, József Balogh, and Robert Morris.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.