TY - JOUR

T1 - The number of hypergraphs without linear cycles

AU - Balogh, József

AU - Narayanan, Bhargav

AU - Skokan, Jozef

N1 - Funding Information:
The first and third authors were partially supported by NSF Grant DMS-1500121 and the first author also wishes to acknowledge support from an Arnold O. Beckman Research Award ( UIUC Campus Research Board 15006 ) and the Langan Scholar Fund ( UIUC ).
Funding Information:
The first and third authors were partially supported by NSF Grant DMS-1500121 and the first author also wishes to acknowledge support from an Arnold O. Beckman Research Award (UIUC Campus Research Board 15006) and the Langan Scholar Fund (UIUC).
Publisher Copyright:
© 2018 Elsevier Inc.

PY - 2019/1

Y1 - 2019/1

N2 - The r-uniform linear k-cycle Ck r is the r-uniform hypergraph on k(r−1) vertices whose edges are sets of r consecutive vertices in a cyclic ordering of the vertex set chosen in such a way that every pair of consecutive edges share exactly one vertex. Here, we prove a balanced supersaturation result for linear cycles which we then use in conjunction with the method of hypergraph containers to show that for any fixed pair of integers r,k≥3, the number of Ck r-free r-uniform hypergraphs on n vertices is 2Θ(nr−1), thereby settling a conjecture due to Mubayi and Wang from 2017.

AB - The r-uniform linear k-cycle Ck r is the r-uniform hypergraph on k(r−1) vertices whose edges are sets of r consecutive vertices in a cyclic ordering of the vertex set chosen in such a way that every pair of consecutive edges share exactly one vertex. Here, we prove a balanced supersaturation result for linear cycles which we then use in conjunction with the method of hypergraph containers to show that for any fixed pair of integers r,k≥3, the number of Ck r-free r-uniform hypergraphs on n vertices is 2Θ(nr−1), thereby settling a conjecture due to Mubayi and Wang from 2017.

KW - Asymptotic enumeration

KW - Balanced supersaturation

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

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

U2 - 10.1016/j.jctb.2018.07.003

DO - 10.1016/j.jctb.2018.07.003

M3 - Article

AN - SCOPUS:85049755853

VL - 134

SP - 309

EP - 321

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -