论文标题
简单与随机常规图上的非简单循环
Simple vs non-simple loops on random regular graphs
论文作者
论文摘要
在本说明中，我们解决了``生日问题''的``生日问题''，以在随机的常规图上循环。也就是说，对于固定的$ d \ ge 3 $，我们证明，在带有$ n $顶点的随机$ d $ graph上，作为$ n $接近无限，具有很高的可能性： （i）几乎所有原始的非折线循环$ k \ prec \ sqrt {n} $都很简单 （ii）几乎所有原始的非折线循环，长度为$ k \ succ \ sqrt {n} $自私。
In this note we solve the ``birthday problem'' for loops on random regular graphs. Namely, for fixed $d\ge 3$, we prove that on a random $d$-regular graph with $n$ vertices, as $n$ approaches infinity, with high probability: (i) almost all primitive non-backtracking loops of length $k \prec \sqrt{n}$ are simple, i.e. do not self-intersect, (ii) almost all primitive non-backtracking loops of length $k \succ \sqrt{n}$ self-intersect.
