On the number of linear hypergraphs of large girth
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.
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}
}
EUVIMED