betaFeedback

WorksMathematics

On the facets of the Cayley polytope of Stanley's triangulation

Abstract

Disjunctions over the cells of a triangulation arise in formulations of piecewise-linear functions. For a poset PP on [d][d], we study the convex hull DD of the simplices of Stanley's triangulation of the order polytope of PP, each lifted by its own indicator vector. Via the Cayley trick, for any disjunction of full-dimensional polytopes, the facets of the convex hull other than those described by the bounds on the indicator variables correspond to the facet normals of the Minkowski sum of the polytopes, and each is described by the full optimal big-M lifting of the supporting inequality with that normal of any one polytope. For Stanley's triangulation, with M(P)M(P) the Minkowski sum of its simplices, lifting only the facet-describing inequalities of the simplices need not suffice, unlike some other cases; we show that it suffices if and only if M(P)M(P) is alcoved, if and only if deleting one element of PP leaves a chain. Otherwise, the coefficients of the additional facet-describing inequalities are governed by the least number ℓ(P)\ell(P) of elements whose deletion leaves a chain: for fixed ℓ(P)\ell(P), the largest entry of a primitive facet normal grows like dℓ(P)−1d^{\ell(P)-1}, and it can be exponential in dd if ℓ(P)\ell(P) grows with dd. For d≥3d \geq 3 and ℓ(P)≤2\ell(P)\leq2 the sharp bound is d−2d-2.

Paper details

vlnc:W_qdwhjsjv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…