On the number of linear hypergraphs of large girth

Research output: Contribution to journalArticlepeer-review

Abstract

An r-uniform linear cycle of length l, denoted by Cr l, is an r-graph with edges e1…el such that for every i ∈ [ℓ − 1], ∣ei ∩ ei+1| = 1, |e ∩ e1| = 1, and ei ∩ ej = ∅ for all other pairs {i, j}, i ≠ j. For every r ≥ 3 and ℓ ≥ 4, we show that there exists a constant C depending on r and l such that the number of linear r-graphs of girth l is at most (Formula presented.). Furthermore, we extend the result for l=4, proving that there exists a constant C depending on r such that the number of linear r -graphs without Cr 4 is at most (Formula presented.). The idea of the proof is to reduce the hypergraph enumeration problems to some graph enumeration problems, and then apply a variant of the graph container method, which may be of independent interest. We extend a breakthrough result of Kleitman and Winston on the number of C4 -free graphs, proving that the number of graphs containing at most n2 32 log6 n C4's is at most (Formula presented.), for sufficiently large n. We further show that for every r ≥ 3 and ℓ ≥ 2, the number of graphs such that each of its edges is contained in only O(1) cycles of length at most 2l, is bounded by (Formula presented.) asymptotically.

Original languageEnglish (US)
Pages (from-to)113-141
Number of pages29
JournalJournal of Graph Theory
Volume93
Issue number1
DOIs
StatePublished - Jan 1 2020

Keywords

  • girth
  • linear cycles
  • linear hypergraphs
  • the graph container method

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'On the number of linear hypergraphs of large girth'. Together they form a unique fingerprint.

Cite this