论文标题
随机平面图中最长和最短周期
Longest and shortest cycles in random planar graphs
论文作者
论文摘要
令$ p（n，m）$是从顶点套装的所有平面图的均匀选择的图形，$ \ {1，\ ldots，n \} $，带有$ m = m（n）$ edges。当$ m \ sim n/2 $时，我们研究$ p（n，m）$的周期和块结构。更确切地说，当$ m = n/2+o（n）$时，我们确定$ p（n，m）$最长和最短周期的长度的渐近顺序。此外，当$ n^{2/3} \ ll m-n/2 \ ll n $时，我们描述了弱超临界制度中$ p（n，m）$的块结构。
Let $P(n,m)$ be a graph chosen uniformly at random from the class of all planar graphs on vertex set $\{1, \ldots, n\}$ with $m=m(n)$ edges. We study the cycle and block structure of $P(n,m)$ when $m\sim n/2$. More precisely, we determine the asymptotic order of the length of the longest and shortest cycle in $P(n,m)$ in the critical range when $m=n/2+o(n)$. In addition, we describe the block structure of $P(n,m)$ in the weakly supercritical regime when $n^{2/3}\ll m-n/2\ll n$.
