Graph properties of DAG associahedra and related polytopes

Abstract: A directed acyclic graph (DAG) can be thought of as encoding a set of conditional independence (CI) relations among random variables. Assuming we sample data from a probability distribution satisfying these CI relations, a fundamental problem in causal inference is to recover the edge-structure of the underlying DAG. An algorithm known as the greedy SP algorithm aims to recover the underlying DAG by walking along edges of a polytope known as the DAG associahedron. Hence, the edge-structure of the DAG associahedron plays an important role in understanding the complexity of the greedy SP algorithm. In this thesis, we study graph properties of the edge-graph of DAG associahedra, related polytopes, and their important subgraphs. The properties considered include diameter, radius and center. Our results on the diameter of DAG associahedra lead to a new causal inference algorithm with improved theoretical consistency guarantees and complexity bounds relative to the greedy SP algorithm.