Let $G$ be a connected, nonbipartite graph on $N$ nodes and $m$ edges. Consider the Markov chain $P_{uv}=\frac{1}{\text{deg}(u)}$. I know that $1$ is always an eiganvalue of $P$ with the eiganvector being the distribution of nodes inversely weighted by their degree.
I'm curious how small the spectral gap $\delta_G =1-\lambda_{\text{max}}$ can be, where $\lambda_{\text{max}}$ is the largest eiganvalue of $P$ that isn't $1$. Is there some sort of statement that lowerbounds $\delta_{N,m}=\min\{\delta_G: G=(V,E)\text{ connected, nonbipartite},|V|=N,|E|=m \}$?
The spectral gap $\delta_G$ is at least $c/Nm$ where $c$ is a constant. Indeed, the mixing time of lazy random walk is on $G$ is $O(Nm)$, see e.g. Chapter 10 in [1]. The inverse gap $\delta_G^{-1}$ is bounded by the mixing time, see chapter 12 there. The bound is attained e.g. for the cycle, where $m=N$ and $\delta_G$ is of order $N^{-2}$, and the barbell graph, where $m=cN^2$ and $\delta_G$ is of order $N^{-3}$.
For an extension to Eulerian digraphs, see [3].
[1] https://yuvalperes.com/markov-chains-and-mixing-times-2/
[2] https://academic.oup.com/imrn/article-pdf/2018/24/7555/27176676/rnx082.pdf
[3] Boczkowski, Lucas, Yuval Peres, and Perla Sousi. "Sensitivity of mixing times in Eulerian digraphs." SIAM Journal on Discrete Mathematics 32, no. 1 (2018): 624-655.