A Nordhaus--Gaddum problem for the spectral gap of a graph

Sooyeong Kim, Neal Madras

Let $G$ be a graph on $n$ vertices, with complement $\overline{G}$. The spectral gap of the transition probability matrix of a random walk on $G$ is used to estimate how fast the r…