论文标题
结构化类的随机图
Random graphs from structured classes
论文作者
论文摘要
给定一个$ \ mathcal g $的图形，令$ {\ mathcal g} _n $表示顶点套装$ [n] $的$ \ natercal g $中的图集。对于某些类$ \ MATHCAL G $，我们对从$ {\ Mathcal G} _n $均匀采样的随机图$ r_n $的渐近行为感兴趣。如果$ n | {\ mathcal g} _ {n-1} |调用$ \ mathcal g $ smooth / | {\ Mathcal G} _n | $趋向于$ n \ to \ infty $。在研究$ r_n $的属性的方法中，表明图表是平滑的，尤其是连接$ r_n $的渐近概率，更一般而言，$ r_n $是$ r_n $的渐近行为。 Bender，Canfield和Richmond的组成方法表明，可以在给定表面中嵌入的图类是光滑的。同样，对于任何少量封闭的图形，我们都具有平稳性，并具有2个连接的不包括未成年人。在这里，我们进一步开发了方法，并给出涵盖这些案例等等的结果。我们看到，在相当普遍的条件下，我们的图形类是平滑的，我们可以描述$ r_n $的片段和核心大小的限制分布；并且我们以最低度至少2个为2。
Given a class $\mathcal G$ of graphs, let ${\mathcal G}_n$ denote the set of graphs in $\mathcal G$ on vertex set $[n]$. For certain classes $\mathcal G$, we are interested in the asymptotic behaviour of a random graph $R_n$ sampled uniformly from ${\mathcal G}_n$. Call $\mathcal G$ smooth if $ n |{\mathcal G}_{n-1}| / |{\mathcal G}_n|$ tends to a limit as $n \to \infty$. Showing that a graph class is smooth is a key step in an approach to investigating properties of $R_n$, in particular the asymptotic probability that $R_n$ is connected, and more generally the asymptotic behaviour of the fragment of $R_n$ outside the largest component. The composition method of Bender, Canfield and Richmond shows that the class of graphs embeddable in a given surface is smooth; and similarly we have smoothness for any minor-closed class of graphs with 2-connected excluded minors. Here we develop the approach further, and give results encompassing both these cases and much more. We see that, under quite general conditions, our graph classes are smooth and we can describe for example the limiting distribution of the fragment of $R_n$ and the size of the core; and we obtain similar results for the graphs in the class with minimum degree at least 2.
