## Abstract

An r-uniform linear cycle of length l, denoted by C^{r} _{l}, is an r-graph with edges e_{1}…e_{l} such that for every i ∈ [ℓ − 1], ∣e_{i} ∩ e_{i+1}| = 1, |e_{ℓ} ∩ e_{1}| = 1, and e_{i} ∩ e_{j} = ∅ 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 C^{r} _{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 C_{4} -free graphs, proving that the number of graphs containing at most n^{2} 32 log^{6} n C_{4}'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 language | English (US) |
---|---|

Pages (from-to) | 113-141 |

Number of pages | 29 |

Journal | Journal of Graph Theory |

Volume | 93 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2020 |

## Keywords

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

## ASJC Scopus subject areas

- Geometry and Topology