TY - JOUR

T1 - The de Bruijn-Erdo″s theorem for hypergraphs

AU - Alon, Noga

AU - Mellinger, Keith E.

AU - Mubayi, Dhruv

AU - Verstraëte, Jacques

N1 - Funding Information:
Acknowledgments We thanks the referees for their comments that helped improve the presentation. Noga Alon—Research supported in part by an ERC Advanced grant and by a USA-Israeli BSF grant. Dhruv Mubayi—Research supported in part by NSF grants DMS-0653946 and DMS-0969092. Jacques Verstraëte— Research supported in part by NSF grant DMS-0800704 and a Hellman Fellowship.

PY - 2012/12

Y1 - 2012/12

N2 - Fix integers n ≤ r ≤ 2. A clique partition of ( r [n] ) is a collection of proper subsets A 1, A 2,.. ., A t ⊂ [n] such that ∪ i ( r Ai) is a partition of ( r [n]). Let cp(n, r) denote the minimum size of a clique partition of ( r [n]). A classical theorem of de Bruijn and Erdo″s 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))n r/2 as n → ∞. 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 ≤ 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) ≤ (nr)/( r q+r-1) 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.

AB - Fix integers n ≤ r ≤ 2. A clique partition of ( r [n] ) is a collection of proper subsets A 1, A 2,.. ., A t ⊂ [n] such that ∪ i ( r Ai) is a partition of ( r [n]). Let cp(n, r) denote the minimum size of a clique partition of ( r [n]). A classical theorem of de Bruijn and Erdo″s 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))n r/2 as n → ∞. 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 ≤ 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) ≤ (nr)/( r q+r-1) 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.

KW - De Bruijn-Erdo″s

KW - Hypergraph

KW - Zarankiewicz problem

UR - http://www.scopus.com/inward/record.url?scp=84868346438&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84868346438&partnerID=8YFLogxK

U2 - 10.1007/s10623-011-9555-4

DO - 10.1007/s10623-011-9555-4

M3 - Article

AN - SCOPUS:84868346438

VL - 65

SP - 233

EP - 245

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

SN - 0925-1022

IS - 3

ER -