Conjectured skeletons and non-adjacencies for partial metric and weighted quasi-metric cones

Let S(n,2)=2n11S(n,2)=2^{n-1}-1 be the Stirling number counting partitions of an nn-element set into two nonempty blocks. For a polyhedral cone, write Sk{\operatorname{Sk}} for its skeleton, KmK_m for the complete graph on mm vertices, Ka,bK_{a,b} for the complete bipartite graph, and ++ for disjoint union. Let \slOCUTn\text{\sl OCUT}_n, \slWQMETn\text{\sl WQMET}_n, and 0,1-\sldWMETn0,1\text{-}\text{\sl dWMET}_n denote the corresponding cones used in the source; δ(S)\delta'(S) and ww' denote the indicated cut and weight vertices.

Skeleton conjecture. (i) Sk(\slOCUTn)=K2S(n,2){{\operatorname{Sk}}}(\text{\sl OCUT}_n)=K_{2S(n,2)} and is a subgraph of Sk(\slWQMETn){{\operatorname{Sk}}}(\text{\sl WQMET}_n). (ii) The complement of Sk(0,1-\sldWMETn){{\operatorname{Sk}}}(0,1\text{-}\text{\sl dWMET}_n) is K1,S(n,2)+S(n,2)K2K_{1,S(n,2)}+S(n,2)K_2; its skeleton has diameter 22, and all non-adjacencies are of the forms (((0));(1))(δ(S);(0))(((0));(1))\nsim(\delta'(S);(0)) and (δ(S);w)(δ(S);w)(\delta'(S);w')\nsim(\delta'(S);w').

The claims concern the adjacency structure of skeleton graphs of cones of oriented cuts, weighted quasi-metrics, and discrete weighted metrics. The paper says that the proofs should be tedious but easy, but the supplied material gives no resolution evidence.

Sources & referencesView supporting material

Primary source

Michel Deza, Elena Deza and Janoš Vidali, “Cones of Weighted and Partial Metrics”, arXiv:1101.0517 (2011).

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.