A nearly tight bound on the probability $G(n,p)$ is even-degenerate

Abstract

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^{-\Omega (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)}$.

arXiv comment9 pages