A nearly tight bound on the probability $G(n,p)$ is even-degenerate
Source: arxiv.org/abs/2611.03444
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)}$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.03444
curl -X POST /api/v1/records/arxiv/2611.03444/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.03444/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'