The de Bruijn-Erdos Theorem for Hypergraphs

Abstract

Fix integers $n\ge r\ge 2$. A clique partition of $\left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ is a collection of proper subsets $A_1,A_2,\dots ,A_t\subset [n]$ such that ${\bigcup }_i\left(\genfrac{}{}{0ex}{}{A_i}{r}\right)$ is a partition of $\left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$. Let $\cp(n,r)$ denote the minimum size of a clique partition of $\left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$. A classical theorem of de Bruijn and Erd\H os states that $\cp(n, 2) = n$. In this paper we study $\cp(n,r)$, and show in general that for each fixed $r\ge 3$, \[ \cp(n,r) \geq (1 + o(1))n^{r/2} \quad \quad \mbox{as}n \rightarrow \infty.\] We conjecture $\cp(n,r) = (1 + o(1))n^{r/2}$. This conjecture has already been verified (in a very strong sense) for $r=3$ by Hartman-Mullin-Stinson. We give further evidence of this conjecture by constructing, for each $r\ge 4$, a family of $(1+o(1))n^{r/2}$ subsets of $[n]$ with the following property: no two $r$-sets of $[n]$ are covered more than once and all but $o(n^r)$ of the $r$-sets of $[n]$ are covered. We also give an absolute lower bound $\cp(n,r) \geq {n \choose r}/{q + r - 1 \choose r}$ when $n=q^2+q+r-1$, and for each $r$ characterize the finitely many configurations achieving equality with the lower bound. Finally we note the connection of $\cp(n,r)$ to extremal graph theory, and determine some new asymptotically sharp bounds for the Zarankiewicz problem.

17 pages