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.
-
Complete description of the metric polytope and cone on 8 nodes
(2003)
-
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