The dual polyhedron to the chordal graph polytope and the rebuttal of the chordal graph conjecture

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F21%3A00545447" target="_blank" >RIV/67985556:_____/21:00545447 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S0888613X21001316?via%3Dihub" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0888613X21001316?via%3Dihub</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ijar.2021.07.014" target="_blank" >10.1016/j.ijar.2021.07.014</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The dual polyhedron to the chordal graph polytope and the rebuttal of the chordal graph conjecture

Popis výsledku v původním jazyce

The integer linear programming approach to structural learning of decomposable graphical models led us earlier to the concept of a chordal graph polytope. An open mathematical question motivated by this research is what is the minimal set of linear inequalities defining this polytope, i.e. what are its facet-defining inequalities, and we came up in 2016 with a specific conjecture that it is the collection of so-called clutter inequalities. In this theoretical paper we give an implicit characterization of the minimal set of inequalities. Specifically, we introduce a dual polyhedron (to the chordal graph polytope) defined by trivial equality constraints, simple monotonicity inequalities and certain inequalities assigned to incomplete chordal graphs. Our main result is that the vertices of this polyhedron yield the facet-defining inequalities for the chordal graph polytope. We also show that the original conjecture is equivalent to the condition that all vertices of the dual polyhedron are zero-one vectors. Using that result we disprove the original conjecture: we find a vector in the dual polyhedron which is not in the convex hull of zero-one vectors from the dual polyhedron.

Název v anglickém jazyce

The dual polyhedron to the chordal graph polytope and the rebuttal of the chordal graph conjecture

Popis výsledku anglicky

The integer linear programming approach to structural learning of decomposable graphical models led us earlier to the concept of a chordal graph polytope. An open mathematical question motivated by this research is what is the minimal set of linear inequalities defining this polytope, i.e. what are its facet-defining inequalities, and we came up in 2016 with a specific conjecture that it is the collection of so-called clutter inequalities. In this theoretical paper we give an implicit characterization of the minimal set of inequalities. Specifically, we introduce a dual polyhedron (to the chordal graph polytope) defined by trivial equality constraints, simple monotonicity inequalities and certain inequalities assigned to incomplete chordal graphs. Our main result is that the vertices of this polyhedron yield the facet-defining inequalities for the chordal graph polytope. We also show that the original conjecture is equivalent to the condition that all vertices of the dual polyhedron are zero-one vectors. Using that result we disprove the original conjecture: we find a vector in the dual polyhedron which is not in the convex hull of zero-one vectors from the dual polyhedron.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA19-04579S" target="_blank" >GA19-04579S: Struktury podmíněné nezávislosti: metody polyedrální geometrie</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

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

Název periodika

International Journal of Approximate Reasoning

ISSN

0888-613X

e-ISSN

1873-4731

Svazek periodika

138

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

16

Strana od-do

188-203

Kód UT WoS článku

000704053400012

EID výsledku v databázi Scopus

2-s2.0-85114479243