Combinatorics Seminar
When: Sunday, November 10, 10am
Where: Schreiber 309
Speaker: Avraham Morgenstern,Hebrew University
Title: On high-dimensional acyclic tournaments
Abstract:
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.