On a problem of Erdos and Moser

-
Alex Scott, Oxford University
Fine Hall 224

A set A of vertices in an r-uniform hypergraph H is ``covered'' in H if, for every (r−1)-set B contained in A, the set B+{u} is an edge of H. Erdos and Moser (1970) determined the minimum number of edges in a graph on n vertices such that every k-set is covered. We extend this result to r-uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs. Joint work with Bela Bollobas.