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,...,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)$. Clique partitions are related to design theory, coding theory, projective geometry, and extremal combinatorics. 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$ and also determines the extremal configurations. 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 {as}n \to \infty.\] We conjecture $\cp(n,r) = (1 + o(1))n^{r/2}$, and prove this conjecture in a very strong sense for $r=3$ by giving a characterization of optimal clique partitions of $\left(\genfrac{}{}{0ex}{}{[n]}{3}\right)$ for infinitely many $n$. Precisely, when $n=q^2+1$ and $q$ is a prime power, we show \[ \cp(n,3) = n\sqrt{n-1} \] and characterize those clique partitions achieving equality. 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.

This paper has been withdrawn by the authors due to the fact that Theorem 1 was proved earlier.

References in corpus (1)

• A Counting Proof of the Graham Pollak Theorem