Adjacency and diameter conjecture for the oriented-multicut skeleton

Let OMCUTnOMCUT_n be the cone of oriented multicuts, and let GOMCUTnG_{OMCUT_n} be its skeleton graph. For an oriented partition AA, write ATA^T for its reversal, and write A<BA<B when AA is a proper refinement of BB; write A<˙BA\mathrel{\dot{<}}B when every part of AA is a proper subset of a part of BB. Let p(n)p'(n) denote the number of oriented-multicut extreme rays.

Oriented-multicut adjacency conjecture. (i) An oriented multicut δ(A)\delta'(A) is not adjacent to every oriented multicut δ(B)\delta'(B) such that B<ATB<A^T. (ii) The orbit represented by the oriented cut δ({1},{2,,n})\delta'(\{1\},\{2,\dots,n\}) is the unique orbit whose extreme rays are not adjacent only to the oriented multicuts described in (i); its total adjacency is p(n)p(n1)1p'(n)-p'(n-1)-1, and this is maximal. (iii) An extreme ray in the orbit represented by δ({1,2},{3,,n})\delta'(\{1,2\},\{3,\dots,n\}) is not adjacent only to oriented multicuts δ(B)\delta'(B) for which either B<({1,2},{3,,n})TB<(\{1,2\},\{3,\dots,n\})^T, or BB is a cyclic shift of some CC with C<˙({1,2},{3,,n})C\mathrel{\dot{<}}(\{1,2\},\{3,\dots,n\}). (iv) The diameter of GOMCUTnG_{OMCUT_n} is 22.

The source gives these as conjectural adjacency properties; no general verification or resolution is supplied in the provided text.

Sources & referencesView supporting material

Primary source

M. Deza, M. Dutour and E. Panteleeva, “Small cones of oriented semi-metrics”, arXiv:math/0111145 (2002).

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.