{
  "id": "1007.4150",
  "version": "v1",
  "published": "2010-07-23T15:16:23.000Z",
  "updated": "2010-07-23T15:16:23.000Z",
  "title": "The de Bruijn-Erdos Theorem for Hypergraphs",
  "authors": [
    "Noga Alon",
    "Keith E. Mellinger",
    "Dhruv Mubayi",
    "Jacques Verstraëte"
  ],
  "comment": "17 pages",
  "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, \\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-07-23T15:16:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65"
    ],
    "keywords": [
      "bruijn-erdos theorem",
      "hypergraphs",
      "clique partition",
      "absolute lower bound",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1007.4150A"
    }
  }
}