Cut polytope
The cut polytope CUT(n) is the convex hull of incidence vectors
of cuts in a undirected graph with n nodes.
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.