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

preprint2020arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.