# Size of Interventional Markov Equivalence Classes in Random DAG Models

arXiv: https://arxiv.org/abs/1903.02054 · HTML: https://mlsanity.com/paper/1903.02054/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2019.

## Built on by (most cited first, 9 of 9)

- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [CausalBench: A Large-scale Benchmark for Network Inference from Single-cell Perturbation Data](https://mlsanity.com/paper/2210.17283/) (2022)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Interventional Fairness on Partially Known Causal Graphs: A Constrained Optimization Approach](https://mlsanity.com/paper/2401.10632/) (2024)
- [Scalable and Flexible Causal Discovery with an Efficient Test for Adjacency](https://mlsanity.com/paper/2406.09177/) (2024)
- [Collaborative Causal Discovery with Atomic Interventions](https://mlsanity.com/paper/2106.03028/) (2021)
- [Causal Discovery under Off-Target Interventions](https://mlsanity.com/paper/2402.08229/) (2024)
- [Lower Bounds on the Size of Markov Equivalence Classes](https://mlsanity.com/paper/2506.20933/) (2025)
- [Theoretical Guarantees for Causal Discovery on Large Random Graphs](https://mlsanity.com/paper/2511.02536/) (2025)

## Abstract (arXiv)

Directed acyclic graph (DAG) models are popular for capturing causal relationships. From observational and interventional data, a DAG model can only be determined up to its interventional Markov equivalence class (I-MEC). We investigate the size of MECs for random DAG models generated by uniformly sampling and ordering an ErdHos-R'enyi graph. For constant density, we show that the expected log observational MEC size asymptotically (in the number of vertices) approaches a constant. We characterize I-MEC size in a similar fashion in the above settings with high precision. We show that the asymptotic expected number of interventions required to fully identify a DAG is a constant. These results are obtained by exploiting Meek rules and coupling arguments to provide sharp upper and lower bounds on the asymptotic quantities, which are then calculated numerically up to high precision. Our results have important consequences for experimental design of interventions and the development of algorithms for causal inference.