论文标题
部分可观测时空混沌系统的无模型预测
Cover time of graphs with bounded genus
论文作者
论文摘要
有限连接的图的覆盖时间是图表上简单随机步行所需的预期步骤数，以访问图形的所有顶点。众所周知，任何有限连接的$ n $ vertex图的封面时间至少为$（1 + o（1））n \ log n $，最多最多$（1 + o（1））\ frac {4} {27} {27} n^3 $。乔纳森（Jonasson）和施拉姆（Schramm）的覆盖时间至少是$ c n（\ log n）^2 $，最多只有$ 6n^2 $，其中$ c $是一个正常的常数，具体仅取决于图的最大程度。特别是，通过在Riemann球上使用平面图的圆形堆积来确定下限。在本文中，我们表明，在紧凑型riemann cubl $ g $的紧凑型$ g $上，任何有限$ n $ vertex $ g $的覆盖时间至少是$ c n（\ log n）^2/δ（g + 1）$，最多是$（6 + O（6 + O（6 + O（6 + o（6 + o），如果是$ c的，如果$ c $ ndtide） $ s $和$ g $填充$ s $的圆包装。
The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all vertices of the graph. It is known that the cover time of any finite connected $n$-vertex graph is at least $(1 + o(1)) n \log n$ and at most $(1 + o(1)) \frac{4}{27} n^3$. By Jonasson and Schramm, the cover time of any bounded-degree finite connected $n$-vertex planar graph is at least $c n(\log n)^2$ and at most $6n^2$, where $c$ is a positive constant depending only on the maximal degree of the graph. In particular, the lower bound is established via the use of circle packing of planar graphs on the Riemann sphere. In this paper, we show that the cover time of any finite $n$-vertex graph $G$ with maximum degree $Δ$ on the compact Riemann surface $S$ of given genus $g$ is at least $c n(\log n)^2/ Δ(g + 1)$ and at most $(6 + o(1))n^2$, where $c$ is an absolute constant, if $n$ is sufficiently large and three sufficient conditions for $S$ and a circle packing of $G$ filling $S$.
