论文标题
任何图的随机嵌入中的预期面数最多是线性的
Expected number of faces in a random embedding of any graph is at most linear
论文作者
论文摘要
通过在每个顶点围绕随机的局部旋转，可以获得给定图$ G $的随机2细胞嵌入。我们分析了这种嵌入的面孔的预期数量，这相当于研究其平均属。 1991年，Stahl证明了随机嵌入订单$ n $的随机嵌入中的预期面部数量最多为$ n \ log（n）$。虽然有许多图表的家庭预期的面孔为$θ（n）$，但没有人知道预期的数字将是超级线性的。这导致猜想是有线性上限。在本说明中，我们通过证明对于任何$ n $ vertex Multigraph的证明，随机2细胞嵌入中的预期面孔数量最多为$ n（1+h_m）$，其中$ m $是最大边缘 - 倍增性和$ h_m $ $ $表示$ M $ m $ m $ th marmonic th marmonic narmonic numboric narmonic numbor。这种界限最好达到恒定因素。
A random 2-cell embedding of a given graph $G$ is obtained by choosing a random local rotation around every vertex. We analyze the expected number of faces of such an embedding, which is equivalent to studying its average genus. In 1991, Stahl proved that the expected number of faces in a random embedding of an arbitrary graph of order $n$ is at most $n\log(n)$. While there are many families of graphs whose expected number of faces is $Θ(n)$, none are known where the expected number would be super-linear. This lead to the conjecture that there is a linear upper bound. In this note we confirm the conjecture by proving that for any $n$-vertex multigraph, the expected number of faces in a random 2-cell embedding is at most $n(1+H_m)$, where $m$ is the maximum edge-multiplicity and $H_m$ denotes the $m$th harmonic number. This bound is best possible up to a constant factor.
