When: Sunday, May 14, 10am
Where: Schreiber 309
Speaker: Nadav Sherman, Tel Aviv U.
Title: Induced Universal Hypergraphs
We prove that for every fixed d \geq 3, the minimum number of vertices of a d-uniform hypergraph that contains every d-uniform hypergraph on k vertices as an induced sub-hypergraph is
N = (1+o(1)) 2^{{k \choose d}/k}.
The proof relies on the probabilistic method and provides a non-constructive solution. In addition we exhibit an explicit construction of such a hypergraph on less than 3N vertices.
Joint work with Noga Alon.
