Isoperimetric invariants for product Markov chains and graph products (Q558240)

Let \(K\) be a Markov kernel on a finite state space \(X\), of invariant measure \(\pi\). For \(1\leq p\leq 2\), let \(h_p(K)\) be the associated Cheeger constant. The relation between the spectral gap \(\lambda(L(K))\), where \(L(K)=I-K\), and \(h_1(K)\) is given by \[ h_1^2(K)/8 \leq \lambda(L(K))\leq h_1(K). \] The authors consider mainly the direct product \(K^n\) of Markov chains \((K_1,\pi_1),\cdots,(K_n,\pi_n)\), namely \[ K^n(x,y)={1\over n}\sum_{i=1}^n\delta_{x_1y_1}\cdots\delta_{x_{i-1}y_{i-1}}K_i(x_i,y_i)\delta_{x_{i+1}y_{i+1}}\cdots \delta_{x_ny_n} \] where \(x=(x_1,\cdots, x_n), y=(y_1, \cdots, y_n)\). They prove that \[ h_p(K^n)\geq 1/(4\sqrt{6}n^{1/p})\min_{1\leq i\leq n}h_1(K_i). \] If \(K_i\) are reversible, \[ h_p(K)\geq 1/(4\sqrt{6}n^{1/n})\min_{1\leq i\leq n}\Bigl( \delta_i^{p-1/p}h_p(K_i)\Bigr) \] where \(\delta_i\) is the smallest positive element in \(\{K_i(x,y)>0: x,y\}\).