Combinatorics Seminar

When: Sunday, May 14, 10am

Where: Schreiber 309

Speaker: Nadav Sherman, Tel Aviv U.

Title: Induced Universal Hypergraphs

Abstract:

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.

redesigned by barak soreq