ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.