Typical structure of hereditary graph families. I. Apex-free families

arXiv2007.00686MaRDI QIDQ6344232FDOQ6344232

Serguei Norine, Yelena Yuditsky

Publication date: 1 July 2020

Abstract: A family of graphs $mathcalF$ is hereditary if $mathcalF$ is closed under isomorphism and taking induced subgraphs. The speed of $mathcalF$ is the sequence ${|mathcal{F}^n|}_{ninmathbbN}$, where $mathcal{F}^n$ denotes the set of graphs in $mathcalF$ with the vertex set $[n]$. Alon, Balogh, Bollob'{a}s and Morris [The structure of almost all graphs in a hereditary property, JCTB 2011] gave a rough description of typical graphs in a hereditary family and used it to show for every proper hereditary family $mathcalF$ there exist $varepsilon>0$ and an integer $lgeq1$ such that ${\displaystyle }$|mathcal{F}^n| = 2^{(1-1/l)n^2/2+o(n^{2-varepsilon})}.${\displaystyle }$ The main result of this paper gives a more precise description of typical structure for a restricted class of hereditary families. As a consequence we characterize hereditary families with the speed just above the threshold $2^{(1-1/l)n^2/2}$, generalizing a result of Balogh and Butterfield [Excluding induced subgraphs: Critical graphs, RSA 2011].

This page was built for publication: Typical structure of hereditary graph families. I. Apex-free families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6344232)