论文标题
在两派的恒定和膨胀Cayley图上
On the Bipartiteness Constant and Expansion of Cayley Graphs
论文作者
论文摘要
令$ g $为有限的，无方向的$ d $ - 规则图和$ a（g）$其正常化的邻接矩阵，eigenvalues $ 1 =λ_1（a）\ geq \ dots \geλ_n\geλ_n\ ge -1 $。这是一个经典的事实，即$λ_n= -1 $，并且仅当$ g $是双方。就其扩展而言，我们的主要结果提供了$ -1 $的$λ_n$的定量分离。用（外边界）顶点扩展为$ g $表示$ h_ {out} $，我们表明，如果$ g $是一个非两部分的cayley图（使用组构建和尺寸$ d $的对称生成集），则$λ_n\ ge -1 + ge -1 + ge -1 + ch_ {out}^2/d^2/d^2/d^2/d^2^2^2^2 \ $ c $ co $ co $ cob an axpect for $ c and axpart。我们展示的图表因$ d $而定为一个因素。 Biswas和Saha的最新结果改善了这一点，他们显示了$λ_n\ ge -1 + h_ {out}^4/（2^9d^8）\，。$，我们还注意到，对于一般的非双层图形，这一结果是不正确的。
Let $G$ be a finite, undirected $d$-regular graph and $A(G)$ its normalized adjacency matrix, with eigenvalues $1 = λ_1(A)\geq \dots \ge λ_n \ge -1$. It is a classical fact that $λ_n = -1$ if and only if $G$ is bipartite. Our main result provides a quantitative separation of $λ_n$ from $-1$ in the case of Cayley graphs, in terms of their expansion. Denoting $h_{out}$ by the (outer boundary) vertex expansion of $G$, we show that if $G$ is a non-bipartite Cayley graph (constructed using a group and a symmetric generating set of size $d$) then $λ_n \ge -1 + ch_{out}^2/d^2\,,$ for $c$ an absolute constant. We exhibit graphs for which this result is tight up to a factor depending on $d$. This improves upon a recent result by Biswas and Saha who showed $λ_n \ge -1 + h_{out}^4/(2^9d^8)\,.$ We also note that such a result could not be true for general non-bipartite graphs.
