Appendix B — Prerequisites

Open source document →

1. #1

   Fact B.1 (Bi-invariant metric). Every compact Lie group admits an -invariant inner product on its Lie algebra . The corresponding left-invariant Riemannian metric on is automatically bi-invariant. The geodesic distance satisfies:

   $$d_G(k\,g\,k',\;k\,h\,k') = d_G(g,h) \quad\forall\,g,h,k,k'\in G.$$
2. #2

   Fact B.3 (Discrete Cheeger inequality). For the Cheeger constant :

   $$\frac{\lambda_2}{2}\;\le\;h\;\le\;\sqrt{2\lambda_2}.$$
3. #3

   Definition. For :

   $$\phi(S)=\frac{\mathrm{cut}(S,\bar S)}{\min\{\mathrm{vol}(S),\mathrm{vol}(\bar S)\}}.$$
4. #4

   Fact B.5 (Conductance and mixing time). For the lazy random walk , the mixing time satisfies:

   $$t_{\mathrm{mix}}(\epsilon)\;\ge\;\frac{1}{2\phi}\ln\frac{1}{2\epsilon}$$
5. #5

   Fact B.6 (Sinclair--Jerrum conductance bound). For a reversible Markov chain with conductance , the spectral gap satisfies:

   $$\frac{\Phi^2}{2}\;\le\;\gamma\;\le\;2\Phi.$$
6. #6

   Fact B.8 (Lojasiewicz inequality, finite-dimensional). Let be a real-analytic function on a compact Riemannian manifold . For every critical value of , there exist and such that in a neighbourhood of :

   $$\|\mathrm{grad}\,f(x)\|\;\ge\;C\,|f(x)-c|^\alpha.$$
7. #7

   Fact B.8 (Lojasiewicz inequality, finite-dimensional). Let be a real-analytic function on a compact Riemannian manifold . For every critical value of , there exist and such that in a neighbourhood of : Consequence.

   $$\int_0^\infty\|\dot x(t)\|\,dt\;<\;\infty.$$