Metraipolis › archive › dc_d4fa8bc40b84

Polyhedral Geometry of Degree-Bounded Characteristic Imset Polytopes — arXiv:2611.09633

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.09633
License (as archived)
CC0-1.0
Archived
2026-11-09T22:42:44.049Z
SHA-256 of the archived text
f99bd36dba37eab1ba8583e25d41eb6ea8062105ae7c66de763f304254bd8918
Stable URL of this page
https://metraipolis.com/documento/dc_d4fa8bc40b84

How to cite

Polyhedral Geometry of Degree-Bounded Characteristic Imset Polytopes — arXiv:2611.09633 — arXiv (en), https://arxiv.org/abs/2611.09633 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d4fa8bc40b84 (Metraipolis archive dc_d4fa8bc40b84, sha256 f99bd36dba37eab1ba8583e25d41eb6ea8062105ae7c66de763f304254bd8918)
BibTeX
@misc{dcd4fa8bc40b84,
  title = {Polyhedral Geometry of Degree-Bounded Characteristic Imset Polytopes — arXiv:2611.09633},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09633},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d4fa8bc40b84; sha256 f99bd36dba37eab1ba8583e25d41eb6ea8062105ae7c66de763f304254bd8918},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09633. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 a matroid independence polytope. For $k = 2$ we provide several large families of facet-defining inequalities, which give a complete $\mathcal{H}$-representation of the polytope on four nodes.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.ST, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2611.09633 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-09T22:35:47.245Z dalla pagina https://arxiv.org/list/math.ST/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).