The de Bruijn-Erdos Theorem for hypergraphs

Abstract: Fix integers

n g e r g e 2

. A clique partition of

[n] c h o o s e r

is a collection of proper subsets

A_{1}, A_{2}, ..., A_{t} s u b s e t [n]

such that

is a partition of

[n] c h o o s e r

. Clique partitions are related to design theory, coding theory, projective geometry, and extremal combinatorics. Let

c p (n, r)

denote the minimum size of a clique partition of

[n] c h o o s e r

. A classical theorem of de Bruijn and ErdH os states that

c p (n, 2) = n

and also determines the extremal configurations. In this paper we study

c p (n, r)

, and show in general that for each fixed

r g e q 3

, [cp(n,r) geq (1 + o(1))n^{r/2} quad quad {as}n o infty.] We conjecture

c p (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

[n] c h o o s e 3

for infinitely many

n

. Precisely, when

n = q^{2} + 1

and

q

is a prime power, we show [ cp(n,3) = nsqrt{n-1} ] and characterize those clique partitions achieving equality. We also give an absolute lower bound

c p (n, r) g e q n c h o o s e r / q + r - 1 c h o o s e 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

c p (n, r)

to extremal graph theory, and determine some new asymptotically sharp bounds for the Zarankiewicz problem.

This page was built for publication: The de Bruijn-Erdos Theorem for hypergraphs