Mathieu Dutour Sikirić

Cut and Metric Cones

This page provides definitions and computational results for various metric and cut cones. For broader context, see the pages by Michel Deza and the SMAPO project.

Definitions

Metric Cone (MET_n): Defined by n(n-1)(n-2)/2 triangle inequalities: x_ij + x_jk - x_ik ≥ 0 for all triples {i,j,k}.
Cut Vector: For any subset S of {1,...,n}, δ(S)_ij = 1 if one element is in S and the other is not, and 0 otherwise.
Cut Cone (CUT_n): The positive span of the 2^n-1-1 non-zero cut vectors.

Computed Metric Cones

All computations were performed using cdd and specialized Perl scripts.

Cones for n=3, 4

Cone	Dim	Group	Extreme Rays	Facets	Details
CUT₃ = MET₃	3	Sym(3)	3 (1 orbit)	3 (1 orbit)	TeX \| PS
CUT₄ = MET₄	6	Sym(4)	7 (2 orbits)	12 (1 orbit)	TeX \| PS

Cones for n=5, 6

Cone	Dim	Group	Extreme Rays	Facets	Details
CUT₅	10	Sym(5)	15 (2 orbits)	40 (2 orbits)	TeX \| PS
MET₅	10	Sym(5)	25 (3 orbits)	30 (1 orbit)	TeX \| PS
CUT₆	15	Sym(6)	31 (3 orbits)	210 (4 orbits)	TeX \| PS
MET₆	15	Sym(6)	296 (7 orbits)	60 (1 orbit)	TeX \| PS

Cones for n=7, 8

Cone	Dim	Group	Extreme Rays	Facets	Details
CUT₇	21	Sym(7)	63 (3 orbits)	38,780 (36 orbits)	TeX \| PS
MET₇	21	Sym(7)	55,226 (46 orbits)	105 (1 orbit)	TeX \| PS
CUT₈	28	Sym(8)	127 (4 orbits)	49,604,520 (2169 orbits)	List
MET₈	28	Sym(8)	119,269,588 (3918 orbits)	168 (1 orbit)	List

Cone for n=9

Dimension: 36 | Group: Sym(9)
Extreme Rays: 255
Facets: At least 12,246,651,158,320 facets in 164,506 classes (under switching and permutation).