Id: arxiv/2611.09633 Url: https://arxiv.org/abs/2611.09633 Tags: math.CO, math.ST Score: 0 Title: Polyhedral Geometry of Degree-Bounded Characteristic Imset Polytopes Domain: math.CO Source: arxiv Authors: Jane Ivy Coons, Ben Hollering, Niharika Chakrabarty Paul Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-06 Page: https://delphi.science/r/arxiv/2611.09633 Characteristic imset polytopes are convex hulls of a collection of characteristic imset vectors, which are 0/1 vectors that encode the Markov equivalence class of a directed acyclic graph. These polytopes are the feasible region of linear programs which correspond to causal discovery problems. We introduce a new family of these polytopes whose vertices correspond to directed acyclic graphs with in-degree bounded by $k$. This yields a polytope whose dimension is only polynomial in the number of nodes of the underlying graphs instead of exponential. We show that when $k = 1$, this polytope is…