Enumeration of the facets of cut polytopes over some highly symmetric graphs

Abstract

We report here a computation giving the complete list of facets for the cut polytopes over several very symmetric graphs with $15-30$ edges, including $K_8$, $K_{3,3,3}$, $K_{1,4,4}$, $K_{5,5}$, some other $K_{l,m}$, $K_{1,l,m}$, $Pris{m}_7,APris{m}_6$, Möbius ladder $M_{14}$, Dodecahedron, Heawood and Petersen graphs. For $K_8$, it shows that the huge lists of facets of the cut polytope $CUT{P}_8$ and cut cone $CU{T}_8$, given in [CR] is complete. We also confirm the conjecture that any facet of $CUT{P}_8$ is adjacent to a triangle facet. The lists of facets for $K_{1,l,m}$ with $(l,m)=(4,4),(3,5),(3,4)$ solve problems (see, for example, [Werner]) in quantum information theory.

arXiv comment8 pages, 1 Figure, 2 Tables