Diameters of the order and chain polytopes of a connected poset

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.MG — Metric Geometry

Contributed by Dave Goel ↗

Version 1 / Nov 16, 2026 / CC BY-SA 4.0

Abstract

For a finite poset PP, Stanley's order polytope O(P)\mathcal O(P) and chain polytope C(P)\mathcal C(P) have the same number of vertices and, by a theorem of Hibi, Li, Sahara and Shikama, the same number of edges. On disconnected posets the diameters of their graphs can differ by any amount, since both diameters add over disjoint unions and already differ on small examples, but on connected posets a computer search of Lee found no difference larger than 11. We show that on connected posets, too, the two diameters can be far apart. For every k≥1k\ge1 we describe a connected poset BkB_k with 3k3k elements whose order polytope has graph diameter kk and whose chain polytope has graph diameter at most ⌊3(k+1)/4⌋\lfloor3(k+1)/4\rfloor; hence the first diameter can exceed the second by any amount. For every n≥4n\ge4 we construct a connected poset PnP_n with 2n2+5n+12n^2+5n+1 elements whose order polytope has graph diameter 22 and whose chain polytope has graph diameter 44. Finally, for every finite poset PP, if the graph of O(P)\mathcal O(P) has diameter at most 22, then the graph of C(P)\mathcal C(P) has diameter at most 44; so 22 is the largest possible difference when the order polytope has graph diameter 22.

Author comments: First version: October 28, 2026. The expanded version of this paper, "The Lee (2026) conjecture on the diameters of order and chain polytopes fails in both directions, and other miscellanea", is at https://doi.org/10.5281/zenodo.23351398 on Zenodo.

Provenance statement

This work was done overwhelmingly by AI models and supervised by the author. The models were Anthropic's Claude and OpenAI's ChatGPT. The author takes full responsibility for the paper.

References

  1. F. Aliniaeifard, C. Benedetti, N. Bergeron, S. X. Li and F. Saliola, Stable set polytopes and their 1-skeleta, arXiv:1804.00360v3, 2021.arXiv
  2. V. Chvátal, On certain polytopes associated with graphs, J. Combin. Theory Ser. B 18 (1975), 138--154.
  3. D. Goel, The Lee (2026) conjecture on the diameters of order and chain polytopes fails in both directions, and other miscellanea, Zenodo, 2026 (expanded version of this paper), https://doi.org/10.5281/zenodo.23351398.DOI
  4. T. Hibi and N. Li, Cutting convex polytopes by hyperplanes, Mathematics 7 (5) (2019), Article 381.
  5. T. Hibi, N. Li, Y. Sahara and A. Shikama, The numbers of edges of the order polytope and the chain polytope of a finite partially ordered set, Discrete Math. 340 (2017), 991--994.
  6. Y. T. Ikebe and A. Tamura, Ideal polytopes and face structures of some combinatorial optimization problems, Math. Programming 71 (1995), 1--15.
  7. J. Lee, A refinement of the edge theorem for order and chain polytopes, arXiv:2610.07413, version 1, October 5, 2026. We cite the numbering of version 1; versions 2 and 3 (October 12 and 24, 2026) withdraw Conjecture 29.arXiv
  8. R. P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1 (1986), 9--23.

Version history

  1. v1 · 19 pagesSubmitted by Dave GoelFirst version: October 28, 2026. The expanded version of this paper, "The Lee (2026) conjecture on the diameters of order and chain polytopes fails in both directions, and other miscellanea", is at https://doi.org/10.5281/zenodo.23351398 on Zenodo.CurrentNov 16, 2026