On a problem of Erdos and Moser

Abstract

A set $A$ of vertices in an $r$-uniform hypergraph $\mathcal H$ is covered in $\mathcal H$ if there is some vertex $u\not\in A$ such that, for every $(r-1)$-set $B\subset A$, the set $\{u\}\cup B$ is in $\mathcal 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.