论文标题
表面抽象三角剖分的均匀抽样程序
A Uniform Sampling Procedure for Abstract Triangulations of Surfaces
论文作者
论文摘要
我们提出了一个从一组平衡三角形的组合异构类型（也称为图形表面）中均匀采样的程序。对于给定的数字$ n $，样品是一组加权的图形编码表面，$ 2N $三角形。 采样过程依赖于图形表面与排列之间的连接以及对称组的基本属性。 我们实施了我们的方法，并根据对我们的抽样过程的1.38亿美元运行的分析提出了许多实验发现，从而产生了图形编码的表面，最高三角形$ 280。 也就是说，我们确定，对于$ n $固定，我们样本的经验平均值$ \ bar {g}（n）$非常接近$ \ bar {g}（n）= \ frac {n -1} {2} {2} {2} {2} - （16.98n -110.61）^{1/4} $。此外，我们提供了实验证据，表明相关的属分布越来越集中于所有可能属的消失部分，因为$ n $倾向于无穷大。最后，我们从数据中观察到，表面衰变的均匀选择的图形编码的平均数量以$ n $中的速率超指定速率为零。
We present a procedure to sample uniformly from the set of combinatorial isomorphism types of balanced triangulations of surfaces - also known as graph-encoded surfaces. For a given number $n$, the sample is a weighted set of graph-encoded surfaces with $2n$ triangles. The sampling procedure relies on connections between graph-encoded surfaces and permutations, and basic properties of the symmetric group. We implement our method and present a number of experimental findings based on the analysis of $138$ million runs of our sampling procedure, producing graph-encoded surfaces with up to $280$ triangles. Namely, we determine that, for $n$ fixed, the empirical mean genus $\bar{g}(n)$ of our sample is very close to $\bar{g}(n) = \frac{n-1}{2} - (16.98n -110.61)^{1/4}$. Moreover, we present experimental evidence that the associated genus distribution more and more concentrates on a vanishing portion of all possible genera as $n$ tends to infinity. Finally, we observe from our data that the mean number of non-trivial symmetries of a uniformly chosen graph encoding of a surface decays to zero at a rate super-exponential in $n$.
