SMAPO

Cut polytope

The cut polytope CUT(n) is the convex hull of incidence vectors of cuts in a undirected graph with n nodes.

References

Note: The facets listed below are as well classified with respect to the symmetry given by the permutations of the nodes as by the symmetry of the permutations of the nodes and in addition by the symmetry of the well known switching operation.

CUT(5)

Status: complete description.
2 classes; 56 facets in total; 40 facets at one vertex.
Vertices.
Classes (node permutations+switching) of facets.
Statistics on facet classes.
Classes (node permutations) of facets.

CUT(6)

Status: complete description.
3 classes; 368 facets in total; 210 facets at one vertex.
Vertices.
Classes (node permutations+switching) of facets.
Statistics on facet classes.
Classes (node permutations) of facets.

CUT(7)

Status: complete description.
11 classes; 116,764 facets in total; 38,780 facets at one vertex.
Vertices.
Classes (node permutations+switching) of facets.
Statistics on facet classes.
Classes (node permutations) of facets.

CUT(8)

Status: conjectured complete description.
147 classes; 217,093,472 facets in total; 49,604,520 facets at one vertex.
Vertices.
Classes (node permutations+switching) of facets.
Statistics on facet classes.
Classes (node permutations) of facets.

CUT(9)

Status: description possibly complete.
164,506 classes; 12,246,651,158,320 facets in total.
Vertices.
Classes (node permutations+switching) of facets. (gzipped file, 2.3 MB)
Statistics on classes.

last change: Nov 09, 1997