The Asymptotic χ‐Boundedness of Hereditary Families
Random Structures & Algorithms · 2026-12 · 69 (4)
DOI: 10.1002/rsa.70119 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 09.11.2026. Verfasst von Bruce Reed und 1 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben. Gefördert von: National Science and Technology Council.
Abstract (Originalsprache)
A family of graphs is asymptotically ‐bounded with bounding function if almost every graph in the family satisfies . A graph is ‐free if it does not contain as an induced subgraph. We ask which hereditary families are asymptotically ‐bounded, and discuss some related questions. We show that for every tree , almost all ‐free graphs satisfy . We show that for every cycle except , almost every ‐free graph satisfies . We show that the ‐free graphs are asymptotically ‐bounded with bounding function .
Förderung
- National Science and Technology Council
Zitieren
APA
Reed, B., & Yuditsky, Y. (2026). The Asymptotic χ‐Boundedness of Hereditary Families. Random Structures & Algorithms, 69(4). https://doi.org/10.1002/rsa.70119
Vancouver
Reed B, Yuditsky Y. The Asymptotic χ‐Boundedness of Hereditary Families. Random Structures & Algorithms. 2026;69(4). doi:10.1002/rsa.70119
BibTeX
@article{Reed2026,
author = {Reed, Bruce and Yuditsky, Yelena},
title = {The Asymptotic χ‐Boundedness of Hereditary Families},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {69},
number = {4},
doi = {10.1002/rsa.70119}
}
EUVIMED