EUVIMEDEUVIMED entdecken
Crossref

On the number of linear hypergraphs of large girth

József Balogh, Lina Li

Journal of Graph Theory · 2020-01 · 93 (1) · 113-141

DOI: 10.1002/jgt.22477 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 26.07.2019. Verfasst von József Balogh und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 24 Literaturangaben. Gefördert von: NSF, UIUC Campus Research Board.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

An ‐uniform linear cycle of length , denoted by , is an ‐graph with edges such that for every , and for all other pairs . For every and , we show that there exists a constant depending on and such that the number of linear ‐graphs of girth is at most . Furthermore, we extend the result for , proving that there exists a constant depending on such that the number of linear ‐graphs without is at most . 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 ‐free graphs, proving that the number of graphs containing at most 's is at most , for sufficiently large . We further show that for every and , the number of graphs such that each of its edges is contained in only cycles of length at most , is bounded by asymptotically.

Förderung

  • NSF
  • UIUC Campus Research Board

Zitieren

APA

Balogh, J., & Li, L. (2020). On the number of linear hypergraphs of large girth. Journal of Graph Theory, 93(1), 113-141. https://doi.org/10.1002/jgt.22477

Vancouver

Balogh J, Li L. On the number of linear hypergraphs of large girth. Journal of Graph Theory. 2020;93(1):113-141. doi:10.1002/jgt.22477

BibTeX
@article{Balogh2020,
  author = {Balogh, József and Li, Lina},
  title = {On the number of linear hypergraphs of large girth},
  journal = {Journal of Graph Theory},
  year = {2020},
  volume = {93},
  number = {1},
  pages = {113--141},
  doi = {10.1002/jgt.22477}
}
Kostenlos starten →