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

About 15 years old · traced to

Let S(n,2)=2n−1−1S(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 w′w' 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.

References

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.