{
  "id": "1006.0745",
  "version": "v2",
  "published": "2010-06-03T21:26:36.000Z",
  "updated": "2010-06-28T14:32:47.000Z",
  "title": "The de Bruijn-Erdos Theorem for hypergraphs",
  "authors": [
    "Keith Mellinger",
    "Dhruv Mubayi",
    "Jacques Verstraete"
  ],
  "comment": "This paper has been withdrawn by the authors due to the fact that Theorem 1 was proved earlier.",
  "categories": [
    "math.CO"
  ],
  "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, ..., 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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-06-28T14:32:47.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bruijn-erdos theorem",
      "hypergraphs",
      "optimal clique partitions",
      "clique partitions achieving equality",
      "absolute lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1006.0745M"
    }
  }
}