Metric Polytopes and Metric Cones

The metric cone M_n is defined by the following 3{n\choose 3} triangle inequalities:
• x_{ij}-x_{ik}-x_{jk} \leq 0

for all triples {i,j,k} subset of {1,...,n}
Then, bounding the latter by the following {n\choose 3} perimeter inequalities,
• x_{ij}+x_{ik}+x_{jk} \leq 2
we obtain the metric polytope m_n. Both polyhedra are {n\choose 2}-dimensional
and closely related to the cut polytope and cut cone and to finite metric spaces.
See [Deza-Fukuda-Pasechnik-Sato 2001] for more details.

Two conjectures

(both hold for n<9, the 1st fails for n=9)

• Dominating set conjecture [Laurent-Poljak 1992]
The 0-1 valued vertices form a dominating set (clique) in the skeleton of the metric polytope.

1221 known orbits under permutations and switchings of vertices made of counterexamples
to the dominating set conjecture for the metric polytope on 9 nodes, see [Deza-Indik 2007] for more details.

• No cut-set conjecture [Deza-Fukuda-Pasechnik-Sato 2001]
For n>5, the 0-1 valued vertices do not form a cut-set in the skeleton of the metric polytope.

Probably complete description of the metric polytope on 9 nodes (2007) (1 056 368 orbits using MPI-OWE , a parallelized orbitwise enumeration algorithm )

(the adjacency of all the 1 056 368 orbits -- except 20 of them -- has been computed)

Facets and Vertices of Metric Polytopes for n<10

metric polytope 3 (dimension 3)

4 facets (1 orbit under permutations and switchings)
4 vertices (1 orbit under permutations and switchings)
orbitwise invariants (incidence, adjacency...)
skeleton (orbitwise adjacency table)
3 extreme rays for the associated metric cone 3

metric polytope 4 (dimension 6)

16 facets (1 orbit under permutations and switchings)
8 vertices (1 orbit under permutations and switchings)
orbitwise invariants (incidence, adjacency...)
skeleton (orbitwise adjacency table)
7 extreme rays for the associated metric cone 4

metric polytope 5 (dimension 10)

40 facets (1 orbit under permutations and switchings)
32 vertices (2 orbits under permutations and switchings)
orbitwise invariants (incidence, adjacency...)
skeleton (orbitwise adjacency table)
25 extreme rays for the associated metric cone 5

metric polytope 6 (dimension 15)

80 facets (1 orbit under permutations and switchings)
554 vertices (3 orbits under permutations and switchings)
orbitwise invariants (incidence, adjacency...)
skeleton (orbitwise adjacency table)
296 extreme rays for the associated metric cone 6

metric polytope 7 (dimension 21)

140 facets (1 orbit under permutations and switchings)
275 840 vertices (13 orbits under permutations and switchings)
orbitwise invariants (incidence, adjacency...)
skeleton (orbitwise adjacency table)
55 226 extreme rays for the associated metric cone 7

metric polytope 8 (dimension 28)

224 facets ( 1 orbit under permutations and switchings)
1 550 825 600 vertices ( 533 orbits under permutations and switchings)
orbitwise invariants (incidence, adjacency...)
skeleton (orbitwise adjacency table)
119 269 588 extreme rays for the associated metric cone 8

metric polytope 9 (dimension 36) description conjectured to be complete (2007)

336 facets (1 orbit under permutations and switchings)
about 100 000 000 000 000 vertices ( 1 056 368 orbits [zip file] under permutations and switchings)

Upper Face Lattice of Metric Polytopes for n<10

metric polytope 4 (dimension 6)

faces of dimension 5 (facets) (1 orbit under permutations and switchings)
faces of dimension 4 (1 orbit under permutations and switchings)
faces of dimension 3 (3 orbits under permutations and switchings)

metric polytope 5 (dimension 10)

faces of dimension 9 (facets) (1 orbit under permutations and switchings)
faces of dimension 8 (2 orbits under permutations and switchings)
faces of dimension 7 (6 orbits under permutations and switchings)

metric polytope 6 (dimension 15)

faces of dimension 14 (facets) (1 orbit under permutations and switchings)
faces of dimension 13 (3 orbits under permutations and switchings)
faces of dimension 12 (10 orbits under permutations and switchings)
faces of dimension 11 (34 orbits under permutations and switchings)

metric polytope 7 (dimension 21)

faces of dimension 20 (facets) (1 orbit under permutations and switchings)
faces of dimension 19 (3 orbits under permutations and switchings)
faces of dimension 18 (13 orbits under permutations and switchings)
faces of dimension 17 (61 orbits under permutations and switchings)

metric polytope 8 (dimension 28)

faces of dimension 27 (facets) (1 orbit under permutations and switchings)
faces of dimension 26 (3 orbits under permutations and switchings)
faces of dimension 25 (14 orbits under permutations and switchings)
faces of dimension 24 (79 orbits under permutations and switchings)
faces of dimension 23 (558 orbits under permutations and switchings)
faces of dimension 22 (4 898 orbits under permutations and switchings)
faces of dimension 21 (43 372 orbits under permutations and switchings)

metric polytope 9 (dimension 36)

faces of dimension 35 (facets) (1 orbit under permutations and switchings)
faces of dimension 34 (3 orbits under permutations and switchings)
faces of dimension 33 (15 orbits under permutations and switchings)

last change: May 15, 2007 by Antoine Deza