Mathematics – Combinatorics
Scientific paper
2006-01-16
Mathematics
Combinatorics
19 pages, 1 figure; filled details of the proof of Theorem 4, made many other small changes
Scientific paper
The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier-Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
Avis David
Imai Hiroshi
Ito Tsuyoshi
No associations
LandOfFree
Generating facets for the cut polytope of a graph by triangular elimination does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Generating facets for the cut polytope of a graph by triangular elimination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating facets for the cut polytope of a graph by triangular elimination will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-523836