University of Cambridge > > Combinatorics Seminar > Independent sets in hypergraphs

Independent sets in hypergraphs

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

  • UserWojciech Samotij (University of Cambridge)
  • ClockThursday 27 October 2011, 14:30-15:30
  • HouseMR12.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity