{"id":"arxiv/2611.03444","url":"https://arxiv.org/abs/2611.03444","tags":["math.CO"],"score":0,"title":"A nearly tight bound on the probability $G(n,p)$ is even-degenerate","domain":"math.CO","source":"arxiv","authors":["Ting-Wei Chao","Bruce Reed"],"reviews":0,"subject":"math.CO","summary":"A graph is even-degenerate if we can order its vertices as $v_1,\\dots,v_n$ so that the number of edges from $v_i$ to $v_1,\\dots,v_{i-1}$ is even for all $i>2$. We show that the probability $G(n,p)$ is even-degenerate is $e^{-Ω(n/\\log\\log n)}$, which is only a factor of $\\log\\log n$ away, in the exponent, from the trivial lower bound $2^{-O(n)}$.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}