Braess's paradox is a famous phenomenon from game theory, stating that in traffic networks, the addition of a new road can sometimes worsen congestion. I will describe a similar phenomenon in random graphs: for typical instances of Erdős–Rényi random graphs $G(n,p)$ with constant edge density $p\in(0,1)$, the addition of a random edge will decrease the spectral gap with positive probability, strictly bounded away from zero. I will show that this problem reduces to a question about the delocalization of eigenvectors of normalized Laplacians of $G(n,p)$, and then describe our new eigenvector delocalization results.
Based on joint work with Ronen Eldan and Miki Racz