The number of hypergraphs without linear cycles

József Balogh, Bhargav Narayanan, Jozef Skokan

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)309-321
Number of pages13
JournalJournal of Combinatorial Theory. Series B
Volume134
DOIs
StatePublished - Jan 2019

Keywords

  • Asymptotic enumeration
  • Balanced supersaturation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The number of hypergraphs without linear cycles'. Together they form a unique fingerprint.

Cite this