The local reversal edge conjecture for characteristic imset polytopes

At least 2 years old · documented by

Let G\mathcal{G} be a directed acyclic graph with skeleton GG, and let ii be a vertex. Define G↓i\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 cG↓ic_{\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 G↓i\mathcal{G}_{\downarrow i} are not Markov equivalent, then

conv⁡(cG,cG↓i)\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.