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

Disjunctions over the cells of a triangulation arise in formulations of piecewise-linear functions. For a poset $P$ on $[d]$, we study the convex hull $D$ of the simplices of Stanley's triangulation of the order polytope of $P$, 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)$ 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)$ is alcoved, if and only if deleting one element of $P$ leaves a chain. Otherwise, the coefficients of the additional facet-describing inequalities are governed by the least number $\ell(P)$ of elements whose deletion leaves a chain: for fixed $\ell(P)$, the largest entry of a primitive facet normal grows like $d^{\ell(P)-1}$, and it can be exponential in $d$ if $\ell(P)$ grows with $d$. For $d \geq 3$ and $\ell(P)\leq2$ the sharp bound is $d-2$.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-10-26
DOI
https://doi.org/10.48550/arxiv.2610.35668
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

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

Jon Lee, Yushan Qu
arXiv (Cornell University)
Advanced Combinatorial Mathematics
preprint

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

Jon Lee, Yushan Qu
preprint en

Abstract

Disjunctions over the cells of a triangulation arise in formulations of piecewise-linear functions. For a poset $P$ on $[d]$, we study the convex hull $D$ of the simplices of Stanley's triangulation of the order polytope of $P$, 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)$ 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)$ is alcoved, if and only if deleting one element of $P$ leaves a chain. Otherwise, the coefficients of the additional facet-describing inequalities are governed by the least number $\ell(P)$ of elements whose deletion leaves a chain: for fixed $\ell(P)$, the largest entry of a primitive facet normal grows like $d^{\ell(P)-1}$, and it can be exponential in $d$ if $\ell(P)$ grows with $d$. For $d \geq 3$ and $\ell(P)\leq2$ the sharp bound is $d-2$.

arXiv (Cornell University)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon