Tail bounds for causal equivalence classes of uniform random DAGs
Let $G_n$ be a uniformly random directed acyclic graph on the labelled vertex set $[n] = \{1, \dots, n\}$, and let $M(G_n)$ be its Markov equivalence class: the set of directed acyclic graphs on $[n]$ with the same skeleton and the same v-structures as $G_n$. Schmid and Sly proved that $$\Pr\bigl(|M(G_n)| > t\bigr) \le C \exp\!\left[-(\log t)^{1 + 1/20}\right]$$ for some constant $C$, every $n$ and every sufficiently large $t$, so that every moment of $|M(G_n)|$ is bounded uniformly in $n$. They note that the power of $\log t$ in such a bound can be at most $2$.
Problem. For every $\varepsilon \in (0,1)$, are there constants $C_\varepsilon < \infty$ and $t_\varepsilon > 1$ such that $$\Pr\bigl(|M(G_n)| > t\bigr) \le C_\varepsilon \exp\!\left[-(\log t)^{2-\varepsilon}\right]$$ for every $n \ge 1$ and every real $t \ge t_\varepsilon$, where $\log$ is the natural logarithm?
Source: Schmid and Sly (2022), the question after Theorem 1.1, whether the power of log t there can be taken arbitrarily close to 2; stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO, ST
- Keywords
- AIM Open Applied Problems, directed acyclic graphs, Markov equivalence classes
References
@misc{schmid2022,
author = {Schmid, Dominik and Sly, Allan},
title = {On the number and size of {M}arkov equivalence classes of random directed acyclic graphs},
year = {2022},
eprint = {2209.04395},
archivePrefix = {arXiv},
note = {Revised 2024 (v2)},
}
@misc{aim-random-dag-equivalence-class-tails,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Tail bounds for causal equivalence classes of uniform random DAGs}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/c9929805cece044705abaaebe1cebddac1ba11a6/problems/516-random-dag-equivalence-class-tails.md},
note = {Entry 516 at commit c992980, 2026-10-05},
}
Resolution claims
Let $G_n$ be uniform among the simple directed acyclic graphs on $n$ labeled vertices. We prove that its Markov equivalence class satisfies \[ (|(G_n)|>t) C[-c(\frac{ t}{ t})^2] \] for all sufficiently large $t$, uniformly in $n$. This implies the upper tail with exponent $2-\varepsilon$ asked for by Schmid and Sly. The main estimate is a Gaussian tail for the number …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Open → Solution claimed | The registry's curators | Tail bounds for Markov equivalence classes of uniform random DAGs v1 recorded from AIM @ 24edaad, paper/main.pdf. |
| 2026-10-13 | Needs verification → Open | The registry's curators | Listed as open: the complete solution claimed in AIM pull request #75 (12 October 2026) has not been reviewed there yet. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00271, "Tail bounds for causal equivalence classes of uniform random DAGs", clopen.solutions.