# Petter Restadh: Edges of the Characteristic Imset Polytope

**Time: **
Wed 2022-09-14 10.15 - 11.15

**Participating: **
Petter Restadh (KTH)

Abstract: The characteristic imset of a directed acyclic graph (DAG) D is a 0/1-vector that encodes the probabilistic model of D. The characteristic imset polytope (CIM_p) is the convex hull of all these vectors and was first introduced by Studený, Hemmecke and Lindner to transform causal discovery into a linear optimization problem. It was recently shown that many algorithms for causal discovery could be interpeted as greedy edge-walks on the faces of CIM_p. In this talk we will discuss these lower dimensional faces of this polytope and see their combinatorial interpretations. We will also showcase some recent results on the edge-structure and discuss what implication these edges can have on causal discovery algorithms. These new edges will also lead us to a connection between the stable set polytope and some particular faces of CIM_p.

This talk is based on the articles *Greedy Causal Discovery is Goemetric *(Linusson-R-Solus, 2021) and *On the Edges of the Characteristic Imset Polytopes *(Linusson-R-Solus, 2022).