Graph properties of DAG associahedra and related polytopes

University essay from KTH/Matematik (Avd.)

Author: Jonas Bederoff Ericksson; [2018]

Keywords: ;

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.

  AT THIS PAGE YOU CAN DOWNLOAD THE WHOLE ESSAY. (follow the link to the next page)