Combinatorics Seminar

When: Sunday, June 1, 10am Where: Schreiber 309 Speaker: Ehud Friedgut, Hebrew University, Title: Random hypergraphs with Ramsey properties

Abstract:

How dense does a random 3-uniform hypergraph have to be so that with high probability every coloring of its edges with two colors contains a monochromatic tetrahedron? The answer is that the density should be such that the expected number of copies of tetrahedra containing a fixed edge is a (large) constant.

For those familiar with works of Rodl and Rucinski from the `90s, dealing with the analogous question for graphs, this answer comes as no surprise. Those who actually read those papers should be slightly nervous about the prospect of generalizing everything to the hypergraph setting, especially the details pertaining to Szemeredi's regularity lemma.

I'll try to give a gentle and self contained overview of the proof, without actually going into all the gory details.

Joint work with Vojtech Rodl and Mathias Schacht.