Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as $$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$ Given some doubly-stochastic Markov chain $P$ on $G$, its conductance $\Phi(P)$ is defined as $$ \Phi(P) = \min_{S\subset V,0<|S|\leq|V|}\frac{\sum_{i\in S,j\in\overline{S}}p_{ij}\pi_i}{\sum_{i\in S}\pi_i} = \min_{S\subset V,0<|S|\leq|V|}\frac{\sum_{i\in S,j\in\overline{S}}p_{ij}}{|S|}, $$ with $\pi$ the stationary distribution ($=1/|V|$ for $P$ doubly-stochastic) of $P$ and $p_{ij}$ its transition probabilities.

One easily sees that for any doubly-stochastic $P$: $\Phi(P)\leq h(G)$. Is it known for which cases $\max_P\Phi(P)=h(G)$, with $P$ doubly-stochastic?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.