The local reversal edge conjecture for characteristic imset polytopes

From papers

Let G\mathcal{G} be a directed acyclic graph with skeleton GG, and let ii be a vertex. Define Gi\mathcal{G}_{\downarrow i} by orienting every edge between ii and a neighbor toward ii, while leaving all other edges as in G\mathcal{G}. Write cGc_\mathcal{G} and cGic_{\mathcal{G}_{\downarrow i}} for their characteristic imsets, and let \CIMG\CIM_G denote the characteristic imset polytope associated with GG. Local reversal edge conjecture. If G\mathcal{G} and Gi\mathcal{G}_{\downarrow i} are not Markov equivalent, then

conv(cG,cGi)\operatorname{conv}\left(c_\mathcal{G},c_{\mathcal{G}_{\downarrow i}}\right)

is an edge of \CIMG\CIM_G. A linear bound on the diameter of \CIMG\CIM_G would follow from this conjecture; the source establishes quadratic bounds in general and linear bounds for trees and for the whole polytope, but does not resolve the conjecture for arbitrary skeletons.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Petter Restadh, “Diameters of the Characteristic Imset Polytopes”, arXiv:2302.03647 (2023).

Solutions 0

No solutions have been posted yet.