2010/07/23 by Noga Alon, Alon, Noga, Keith E. Mellinger +5
Computer Science · Engineering · Mathematics · #05C65 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05C65
paper · pdf · doi:10.48550/arxiv.1007.4150
17 pages
arxiv created 2010/07/23 · openalex publication_date 2010/07/23 · arxiv updated 2010/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Fix integers n ≥ r ≥ 2. A clique partition of [n] \choose r is a collection of proper subsets A1, A2, …, At ⊂ [n] such that \bigcupiAi \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 ≥ 3, \cp(n,r) ≥ (1 + o(1))nr/2 asn → ∞. We conjecture \cp(n,r) = (1 + o(1))nr/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 ≥ 4, a family of (1+o(1))nr/2 subsets of [n] with the following property: no two r-sets of [n] are covered more than once and all but o(nr) of the r-sets of [n] are covered. We also give an absolute lower bound \cp(n,r) ≥ n \choose r/q + r - 1 \choose r when n = q2 + 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.