A refinement of the edge theorem for order and chain polytopes
Abstract
For a finite poset, we partition the edges of the order polytope and of the chain polytope into classes indexed by the connected convex subsets of the poset, and we establish that corresponding classes have the same cardinality. This yields a closed formula for the common number of edges, and it identifies the bijection of Hibi, Li, Sahara and Shikama as a disjoint union of simple bijections between corresponding classes, explaining why it is a bijection and how it acts on edge directions and lengths. As consequences, the two polytopes have equally many edge directions, with matching multiplicities, and, for every m, equally many pairs of vertices whose symmetric difference has m components; the chain polytope has at least as many edges parallel to each coordinate subspace as the order polytope; and the edge lengths of the chain polytope are dominated by those of the order polytope, with strict inequality in the last two comparisons exactly when the poset contains a three-element chain. We discuss implications for linear and convex combinatorial optimization over ideals and antichains. We also express the number of edges in terms of the comparability graph, extending to stable-set polytopes of all graphs; give a recursion for series-parallel posets and closed formulas for layered, zigzag and crown posets; and characterize the distributive lattices for which the two polytopes are unimodularly equivalent. Finally, either diameter can exceed the other arbitrarily; both are bounded by the width, and they coincide for series-parallel, zigzag and crown posets.
Related
BibTeX
@misc{lee2026refinement,
title = {{A refinement of the edge theorem for order and chain polytopes}},
author = {Jon Lee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07413},
eprint = {2610.07413},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07413},
}
RIS
TY - UNPB
TI - A refinement of the edge theorem for order and chain polytopes
AU - Jon Lee
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.07413
UR - https://arxiv.org/abs/2610.07413
AB - For a finite poset, we partition the edges of the order polytope and of the chain polytope into classes indexed by the connected convex subsets of the poset, and we establish that corresponding classes have the same cardinality. This yields a closed formula for the common number of edges, and it identifies the bijection of Hibi, Li, Sahara and Shikama as a disjoint union of simple bijections between corresponding classes, explaining why it is a bijection and how it acts on edge directions and lengths. As consequences, the two polytopes have equally many edge directions, with matching multiplicities, and, for every m, equally many pairs of vertices whose symmetric difference has m components; the chain polytope has at least as many edges parallel to each coordinate subspace as the order polytope; and the edge lengths of the chain polytope are dominated by those of the order polytope, with strict inequality in the last two comparisons exactly when the poset contains a three-element chain. We discuss implications for linear and convex combinatorial optimization over ideals and antichains. We also express the number of edges in terms of the comparability graph, extending to stable-set polytopes of all graphs; give a recursion for series-parallel posets and closed formulas for layered, zigzag and crown posets; and characterize the distributive lattices for which the two polytopes are unimodularly equivalent. Finally, either diameter can exceed the other arbitrarily; both are bounded by the width, and they coincide for series-parallel, zigzag and crown posets.
ER -