On a problem of Erdős and Moser (Q1688260)

Let \(H\) be an \(r\)-uniform hypergraph and \(A \subseteq V(H)\). Say \(A\) is covered in \(H\) if there exists a vertex \(u \notin A\) such that \(\{u\} \cup B\) is an edge for every \((r-1)\)-set contained in \(A\). Let \(f(n,k,r)\) be the minimum number of edges in an \(n\)-vertex \(r\)-uniform hypergraph such that every \(k\)-set of vertices is covered. For graphs (that is, \(2\)-uniform hypergraphs), this was investigated by \textit{P. Erdős} and \textit{L. Moser} [J. Aust. Math. Soc. 11, 42--47 (1970; Zbl 0187.21004)], who found the exact value of \(f(n,k,2)\) for all \(n > k\). The authors find the value of \(f(n,k,r)\) for all fixed \(k\) and \(r\) and \(n\) sufficiently large, and they also determine the extremal graphs. The values of \(f(n,k,r)\) are given in terms of the function \(D(n,r)\), which is defined as the minimum number of edges in an \(n\)-vertex \(r\)-uniform hypergraph where every \((r-1)\)-set of vertices is contained in some edge. No closed-form for \(D(n,r)\) is known, but the function is well-studied: its asymptotics were determined by \textit{V. Rödl} [Eur. J. Comb. 6, 69--78 (1985; Zbl 0565.05016)], and its value is known for those \(n\) such that Steiner systems \(S(r-1,r,n)\) exist, these are now known to be infinitely many by results by \textit{P. Keevash} [``The existence of designs'', Preprint, \url{arxiv:1401.3665}] and \textit{S. Glock} et al. [``The existence of designs via iterative absorption: hypergraph \(F\)-designs for arbitrary \(F\)'', Preprint, \url{arXiv:1611.06827}]. The authors also investigate similar problems in the context of oriented graphs and digraphs.