| 概要 | The Perron-Frobenius theorem guarantees that a finite
stochastic Matrix  satisfying the reversibility
condition has a real valued eigenbasis with eigenvalues
>\lambda_1(P)\geq\cdots\geq\lambda_{n-1}(P)\geq -1) .
The spectral gap ) governs key properties of
the associated random walk. Several authors have shown lower bounds
on this gap in terms of geometric quantities on the underlying state
space, known as Cheeger inequalities. We show sharp Cheeger-like lower
bounds on  , both in the edge-expansion sense of Jerrum and
Sinclair, the vertex-expansion notion of Alon, and a mixture of
both. Cheeger-like lower bounds on  follow as well,
in terms of a notion of a fairly natural notion of edge-expansion
which is yet entirely new.
|