论文标题
遗传图家庭的典型结构。 I. Apex-free families
Typical structure of hereditary graph families. I. Apex-free families
论文作者
论文摘要
如果$ \ Mathcal {f} $在同构中关闭并采用诱导的子图，则图形$ \ Mathcal {F} $是遗传性的。 $ \ MATHCAL {F} $的速度是序列$ \ {| \ Mathcal {f}^n | \} _ {n \ in \ Mathbb {n}} $，其中$ \ Mathcal {f}^n $表示$ \ m athcal $ f} $的$ \ n $表示图表的集合。 Alon，Balogh，Bollobás和Morris [遗传性财产中几乎所有图形的结构，JCTB 2011]]对遗传家庭中的典型图进行了粗略描述，并用它显示了每个适当的遗传家庭$ \ Mathcal $ \ Mathcal {f} $都存在$ \ varepsilon> $ \ varepsilon> 0 $ unteger $ l。 $$ | \ MATHCAL {f}^n | = 2^{（1-1/l）n^2/2+o（n^{2- \ varepsilon}）}。结果，我们描述了遗传家庭的速度高于阈值$ 2^{（1-1/l）n^2/2} $，从而推广了Balogh和Butterfield的结果[不包括引起的子图：关键图：RSA 2011]。
A family of graphs $\mathcal{F}$ is hereditary if $\mathcal{F}$ is closed under isomorphism and taking induced subgraphs. The speed of $\mathcal{F}$ is the sequence $\{|\mathcal{F}^n|\}_{n \in \mathbb{N}}$, where $\mathcal{F}^n$ denotes the set of graphs in $\mathcal{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 $\mathcal{F}$ there exist $\varepsilon>0$ and an integer $l \geq 1$ such that $$|\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)n^2/2}$, generalizing a result of Balogh and Butterfield [Excluding induced subgraphs: Critical graphs, RSA 2011].
