The de Bruijn-Erdos Theorem for Hypergraphs

Noga Alon, Keith E. Mellinger, Dhruv Mubayi, Jacques VerstraëtearXiv 2010 · DOI · arXiv

TL;DR

This paper generalizes the classical de Bruijn-Erdős theorem from standard graphs to hypergraphs. It establishes that the minimum number of "cliques" needed to partition all $r$-element subsets of an $n$-element set grows as $n^{r/2}$, providing a new lower bound and a construction that suggests this bound is asymptotically tight.

What Problem Does This Paper Address?

In 1948, mathematicians Nicolaas de Bruijn and Paul Erdős proved a fundamental result in combinatorial geometry: to partition all the edges of a complete graph with $n$ vertices into smaller complete subgraphs (cliques), you need at least $n$ of them. This is a cornerstone of "design theory," where researchers look for ways to cover sets of elements with specific patterns.

However, graphs only deal with pairs of vertices. What happens if we look at triples, quadruples, or $r$-tuples? These higher-order structures are called hypergraphs. The "clique partition number," denoted as $cp(n, r)$, is the minimum number of subsets needed such that every possible $r$-element subset of $n$ vertices is contained in exactly one of those subsets.

While the case for pairs ($r=2$) has been solved for decades, the behavior for $r \ge 3$ remained elusive. This paper aims to determine how $cp(n, r)$ scales as $n$ gets very large.

Methods

The authors employ a combination of combinatorial induction, finite geometry, and algebraic constructions:

  • Inductive Lower Bounds: They use the known values for smaller $r$ to build a recursive lower bound for larger $r$. This involves clever applications of the Chebyshev Sum Inequality and Jensen's Inequality to show that any partition must be "expensive" in terms of the number of cliques used.
  • Finite Geometry: For $r=3$, the problem is deeply connected to inversive planes—geometric structures where "points" and "circles" satisfy specific axioms. The authors provide an elementary construction of these planes using finite field arithmetic.
  • Algebraic Constructions: To provide an upper bound (a way to actually build these partitions), they use polynomials over finite fields. By treating vertices as points in a plane and cliques as the graphs of polynomials, they create a family of subsets that covers almost all $r$-sets without any overlaps.
  • Steiner Systems: The paper analyzes equality cases using Steiner systems—highly symmetric combinatorial designs where every $t$-subset is covered exactly once by a $k$-subset.

Datasets

As a theoretical mathematics paper, it does not use empirical datasets. Instead, it relies on abstract mathematical structures like finite fields ($\mathbb{F}_q$), projective planes, and Steiner systems.

Key Insights and Ideas

  • The $n^{r/2}$ Scaling: The most significant insight is that the complexity of partitioning hypergraphs jumps significantly from the graph case. While $r=2$ requires $n$ cliques, $r=3$ requires roughly $n^{1.5}$, and in general, the number grows as $n^{r/2}$.
  • Asymptotic Sharpness: The authors conjecture that $cp(n, r) \approx n^{r/2}$ is the "true" answer. They provide strong evidence by constructing "near-partitions" that cover all but a vanishingly small fraction ($o(n^r)$) of the required sets using exactly this many cliques.
  • Geometric Rigidity: The paper shows that achieving the absolute minimum number of cliques is extremely rare. For $r \ge 3$, equality only happens for a handful of specific, famous mathematical objects like the Witt designs (associated with the Mathieu groups).
  • The Zarankiewicz Connection: They uncover a tight link between clique partitions and the Zarankiewicz problem, which asks for the maximum number of edges in a bipartite graph that avoids certain complete bipartite subgraphs ($K_{s,t}$). This allows them to solve specific cases of the Zarankiewicz problem that were previously open.

Key Results

  • General Lower Bound: For any fixed $r \ge 3$, the authors prove $cp(n, r) \ge (1 + o(1))n^{r/2}$ as $n \to \infty$.
  • Optimal $r=3$ Case: They confirm that for $n = q^2 + 1$ (where $q$ is a prime power), $cp(n, 3) = q(q^2+1) \approx n^{1.5}$, achieved by inversive planes.
  • Near-Optimal Construction: For $r \ge 4$, they construct a family of $(1+o(1))n^{r/2}$ cliques that partition almost all $r$-sets of $[n]$.
  • Zarankiewicz Bounds: They determine new asymptotically sharp bounds for $z(m, n, 2, r)$, showing that when $m \approx n^{r/2}$, the maximum number of edges is $(1+o(1))\sqrt{nm}$.

Limitations and Future Work

The primary limitation is the "gap" between the near-partition and a full partition for $r \ge 4$. While the authors can cover almost all $r$-sets with the predicted number of cliques, completing the partition to cover the final few sets might require many more small cliques.

The authors formally conjecture that $cp(n, r) = (1 + o(1))n^{r/2}$ for all $r$, but a full proof for $r \ge 4$ remains an open challenge. Additionally, characterizing the optimal configurations for values of $n$ that don't allow for perfect Steiner systems is a difficult problem for future research.

Summary updated

Abstract

Fix integers $n \ge r \ge 2$. A clique partition of ${[n] \choose r}$ is a collection of proper subsets $A_1, A_2, \ldots, A_t \subset [n]$ such that $\bigcup_i{A_i \choose r}$ is a partition of ${[n] \choose r}$. Let $\cp(n,r)$ denote the minimum size of a clique partition of ${[n] \choose r}$. 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 \geq 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.
BibTeX
@misc{alon2010de,
  author = {Noga Alon and Keith E. Mellinger and Dhruv Mubayi and Jacques Verstraëte},
  title = {{The de Bruijn-Erdos Theorem for Hypergraphs}},
  year = {2010},
  eprint = {1007.4150},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1007.4150},
}
Figure