PreprintCC BY-NC-SA 4.0arXiv
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 v1,…,vn so that the number of edges from vi to v1,…,vi−1 is even for all i>2. We show that the probability G(n,p) is even-degenerate is e−Ω(n/loglog n), which is only a factor of loglog n away, in the exponent, from the trivial lower bound 2−O(n).
Related
- Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks
- On the probability that a random Latin square is all-even
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- Halving the original Kalton--Roberts upper bound for nearly additive set functions
- Tight upper bound on dGH(S1,S2k+1): GPT's short proof
BibTeX
@misc{chao2026nearly,
title = {{A nearly tight bound on the probability $G(n,p)$ is even-degenerate}},
author = {Ting-Wei Chao and Bruce Reed},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03444},
eprint = {2611.03444},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03444},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - A nearly tight bound on the probability G(n,p) is even-degenerate
AU - Ting-Wei Chao
AU - Bruce Reed
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03444
UR - https://arxiv.org/abs/2611.03444
AB - A graph is even-degenerate if we can order its vertices as v_1,…,v_n so that the number of edges from v_i to v_1,…,v_i−1 is even for all i>2. We show that the probability G(n,p) is even-degenerate is e^−Ω(n/loglog n), which is only a factor of loglog n away, in the exponent, from the trivial lower bound 2^−O(n).
ER -