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

2020/07/01 by Sergey Norin, Norin, Sergey, Yelena Yuditsky +1
Mathematics · Computer Science · #Graph theory and applications #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2007.00686

Abstract

A family of graphs F is hereditary if F is closed under isomorphism and taking induced subgraphs. The speed of F is the sequence \|Fⁿ|\_{n ∈ ℕ}, where Fⁿ denotes the set of graphs in F with the vertex set [n]. Alon, Balogh, Bollobá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 F there exist ε>0 and an integer l ≥ 1 such that |Fⁿ| = 2^(1-1/l)n²/2+o(n^2-ε). 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)n2/2, generalizing a result of Balogh and Butterfield [Excluding induced subgraphs: Critical graphs, RSA 2011].

Related

• The structure of almost all graphs in a hereditary property
• Typical structure of hereditary graph families. II. Exotic examples
• Hereditary properties of combinatorial structures: posets and oriented graphs
• Edge-apexing in hereditary classes of graphs
• Subgraphs of random graphs in hereditary families