论文标题
具有最小光谱差距的四分之一图
Quartic Graphs with Minimum Spectral Gap
论文作者
论文摘要
Aldous和Fill猜想，在连接的常规图上随机步行的最大放松时间是$（1+O（1））\ frac {3n^2} {2π^2} $。 This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected $k$-regular graph on $n$ vertices is at least $(1+o(1))\frac{2kπ^2}{3n^2}$, and the bound is attained for at least one value of $k$.我们确定具有最小频谱差距的$ N $顶点上连接的四分之一图的结构，这使我们能够证明$ N $ VERTICES上连接的四分之一图的最小频谱差距为$（1+O（1+O（1））\ frac {4π^2} {N^2} {N^2} $。从这个结果，Aldous-填充猜想以$ k = 4 $。
Aldous and Fill conjectured that the maximum relaxation time for the random walk on a connected regular graph with $n$ vertices is $(1+o(1)) \frac{3n^2}{2π^2}$. This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected $k$-regular graph on $n$ vertices is at least $(1+o(1))\frac{2kπ^2}{3n^2}$, and the bound is attained for at least one value of $k$. We determine the structure of connected quartic graphs on $n$ vertices with minimum spectral gap which enable us to show that the minimum spectral gap of connected quartic graphs on $n$ vertices is $(1+o(1))\frac{4π^2}{n^2}$. From this result, the Aldous--Fill conjecture follows for $k=4$.
