The de Bruijn-Erdős 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}, l d o t s, A_{t} s u b s e t [n]

such that

is a partition of

[n] c h o o s e r

. 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

. 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 mbox{as}n ightarrow infty.] We conjecture

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

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.

Recommendations

Cites Work

Cited In (11)

This page was built for publication: The de Bruijn-Erdős theorem for hypergraphs