论文标题
关于随机常规图的属
On the Genus of Random Regular Graphs
论文作者
论文摘要
图的属是一种拓扑不变的，可以测量表面的最小属，该表面可以嵌入图，而无需任何边缘交叉。图属在拓扑图理论中起着基本作用，用于对不同类型的图形及其特性进行分类和研究。我们表明，对于任何整数$ d \ geq 2 $，$ n $ nodes上的随机$ d $ regular Graph的属为$ \ frac {（d -2）} {4} n（1- \ varepsilon）$，对于任何$ \ varepsilon> 0 $，具有很高的可能性。
The genus of a graph is a topological invariant that measures the minimum genus of a surface on which the graph can be embedded without any edges crossing. Graph genus plays a fundamental role in topological graph theory, used to classify and study different types of graphs and their properties. We show that, for any integer $d \geq 2$, the genus of a random $d$-regular graph on $n$ nodes is $\frac{(d - 2)}{4}n(1 - \varepsilon) $ with high probability for any $\varepsilon > 0$.
