Dual formulation of the chordal graph conjecture

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F21%3A00539983" target="_blank" >RIV/67985556:_____/21:00539983 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Dual formulation of the chordal graph conjecture
Original language description
The idea of an integer linear programming approach to structural learning of decomposable graphical models led to the study of the so-called chordal graph polytope. An open mathematical question is what is the minimal set of linear inequalities defining this polytope. Some time ago we came up with a specific conjecture that the polytope is defined by so-called clutter inequalities. In this theoretical paper we give a dual formulation of the conjecture. Specifically, we introduce a certain dual polyhedron defined by trivial equality constraints, simple monotonicity inequalities and certain inequalities assigned to incomplete chordal graphs. The main result is that the list of (all) vertices of this bounded polyhedron gives rise to the list of (all) facet-defining inequalities of the chordal graph polytope. The original conjecture is then equivalent to a statement that all vertices of the dual polyhedron are zero-one vectors. This dual formulation of the conjecture offers a more intuitive view on the problem and allows us to disprove the conjecture.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA19-04579S" target="_blank" >GA19-04579S: Conditonal independence structures: methods of polyhedral geometry</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of Machine Learning Research, Volume 138: International Conference on Probabilistic Graphical Models, 23-25 September 2020, Hotel Comwell Rebild Bakker, Skørping, Denmark
ISBN
—
ISSN
2640-3498
e-ISSN
2640-3498
Number of pages
12
Pages from-to
449-460
Publisher name
JMLR, Inc. and Microtome Publishing
Place of publication
Brookline
Event location
Skørping
Event date
Sep 23, 2020
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—

Similar results(10)