{"id":"arxiv/2610.24143","url":"https://arxiv.org/abs/2610.24143","tags":["math.CO","cs.DM","cs.SI","math.PR"],"score":0,"title":"The Kemeny-Braess Paradox in Random Graphs","domain":"math.CO","source":"arxiv","authors":["Manuel Bodirsky","Lorenzo Ciardo","Mihyun Kang"],"reviews":0,"subject":"math.CO","summary":"In 2016, Kirkland and Zeng initiated the mathematical treatment of Braess paradox for random walks on graphs using Kemeny's constant as the measure of travel time. We study this phenomenon for the Erdős-Rényi random graph $G(n,p)$. An edge in a connected graph is called Kemeny-Braess if its deletion preserves connectedness and decreases Kemeny's constant, while a nonedge is Kemeny-Braess if its insertion increases Kemeny's constant. Let $\\bar d=(n-1)p$ be the expected degree of $G\\sim G(n,p)$, and assume that $\\bar d-\\log n\\to\\infty$, so that $G$ is connected with high probability. We…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-16","reactions":{}}