The de Bruijn-Erdos Theorem for hypergraphs

Details The de Bruijn-Erdos Theorem for hypergraphs The de Bruijn-Erdos Theorem for hypergraphs

2010-06-03

arxiv.org/abs/1006.0745v2

Mathematics

Combinatorics

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

Scientific paper

Fix integers $n \ge r \ge 2$. A clique partition of ${[n] \choose r}$ is a collection of proper subsets $A_1, A_2, ..., A_t \subset [n]$ such that $\bigcup_i{A_i \choose r}$ is a partition of ${[n] \choose r}$. 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 ${[n] \choose r}$. 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 \geq 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 ${[n] \choose 3}$ 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.

Affiliated with

Also associated with

No associations

Rating

The de Bruijn-Erdos Theorem for hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The de Bruijn-Erdos Theorem for hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The de Bruijn-Erdos Theorem for hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-722380