Combinatorics Seminar

When: Sunday, November 10, 10am
Where: Schreiber 309
Speaker: Avraham Morgenstern,Hebrew University
Title: On high-dimensional acyclic tournaments


We present various high-dimensional analogs for the notion of an acyclic (aka transitive) tournament. I will discuss the inter-relations among these notions. I will prove upper and lower bounds on the number of d-dimensional n-vertex acyclic tournaments and deduce a high-dimensional analog of the Erdos-Moser theorem (every n-vertex tournament contains an acyclic subtournament on log n vertices and this is tight up to a factor of (2+o(1))).

Joint work with Nati Linial.