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\notin 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.