# Cut polytope

## Contents

### Introduction

This article introduces the polytope of cuts in a graph. Understanding its geometry is not only interesting from a theoretical point of view, but also necessary in order to be able to design an effective branch-and-cut algorithm for the max-cut problem. The latter can be used for determining exact ground states of Ising spin glasses, cf. the article about the computation of exact ground states of Ising spin glasses.

### Definitions

The cut polytope is the convex hull of the incidence vectors of cuts in a graph. An explanation is given in the following.

Let be the cut associated with node set of a graph . With each cut, we can associate a so-called incidence vector of dimension that contains an entry for each edge in . In case edge is in the cut, the corresponding entry is 1, otherwise it is 0. In formulas, let the incidence vector for a cut be defined by

Let us associate with each of the 2^{|V|-1} many cuts in their corresponding incidence vectors. The latter are 0-1 vectors living in -dimensional space. Taking the convex hull of all incidence vectors of cuts in , we get the cut polytope :

- .

### Examples

#### Example (cut polytope for a graph consisting of a triangle)

The smallest interesting example for a cut polytope can be found for a graph that is a cycle of length three (a triangle), see Figure 1.

- Error creating thumbnail: File missing

For the triangle, we have four different cuts. Let us order the coordinates as , where e.g., refers to the edge between node .

The set of characteristic cut vectors for the triangle in Figure 1 is

- .

In Figure 2 we show the cut polytope for the graph of Figure 1 .

- Error creating thumbnail: File missing

Understanding the geometry of the cut polytope in higher dimensions is essential for the design of an effective branch-and-cut algorithm for max-cut.