We study facets of the k-partition polytope Pk,n, the convex hull of edges cut by r-partitions of a complete graph for r ≤ k, k ≥ 3. We generalize the hypermetric and cycle inequalities (see Deza and Laurent, 1992) from the cut polytope to Pk,n, k ≥ 3. We give some sufficient conditions under which these are facet defining. We show the anti-web inequality introduced by Deza and Laurent (1992) to be facet defining for Pk,n, k ≥ 3. We also give lifting procedures for constructing facets of Pk,r from facets of Pk,n for r ≥ n + 1 and facets of Pk,r from facets of Pk-1,n for r ≥ n + 1.
- Valid inequality
- k-partition polytope
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics