Adjacency and diameter conjecture for the ridge graph of the quasi-semimetric cone

From papers

Let QMETnQMET_n be the cone of quasi-semimetrics, with triangle facets, non-negativity facets NNijNN_{ij}, and ridge graph GQMETnG^{*}_{QMET_n} whose nodes are the facets of QMETnQMET_n and whose edges join adjacent facets. Two vectors are conflicting if they have components with nonzero values of different signs.

Adjacency and diameter conjecture. (i) A triangle facet is adjacent to a facet if and only if they are non-conflicting. (ii) The non-negativity facets NNijNN_{ij} and NNijNN_{i'j'} are adjacent if and only if neither i=ji'=j nor j=ij'=i. (iii) The diameter of GQMETnG^{*}_{QMET_n} is 22. (iv) The ridge graph GQMETnG^{*}_{QMET_n} is an induced subgraph of GOMCUTnG^{*}_{OMCUT_n}.

These assertions were checked by computer for n7n\leq 7. The diameter assertion follows formally from the proposed adjacency criteria together with the preceding non-adjacency results, but the general adjacency and induced-subgraph claims remain open.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.