\documentclass[11pt]{amsart} \usepackage[T1]{fontenc} \usepackage{lmodern,amsmath,amssymb,amsthm,mathtools} \usepackage[margin=1.05in]{geometry} \usepackage{enumitem,booktabs,needspace,array} \usepackage{tikz} \usepackage[hidelinks]{hyperref} \renewcommand{\UrlBreaks}{\do\/} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{question}[theorem]{Question} \newcommand{\OP}{\mathcal O} \newcommand{\CP}{\mathcal C} \newcommand{\sd}{\mathbin{\triangle}} \newcommand{\Iso}{\mathrm{Iso}} \newcommand{\bw}[1]{\mbox{\texttt{#1}}} \newcommand{\emp}{\mbox{\texttt{-}}} \DeclareMathOperator{\diam}{diam} \setlist[enumerate]{leftmargin=*,label=\textup{(\roman*)}} \emergencystretch=2em \raggedbottom \hypersetup{pdftitle={Diameters of the order and chain polytopes of a connected poset},pdfauthor={Dave Goel},pdfkeywords={order polytope, chain polytope, finite poset, graph of a polytope, diameter}} \title[Diameters of order and chain polytopes]{Diameters of the order and chain polytopes of a connected poset} \author{Dave Goel} \email{david44hello@gmail.com} \thanks{\raggedright The Lean~4 proof of Theorems~\ref{thm:main}, \ref{rv-thm:main} and~\ref{rv-thm:upper}, which takes the edge criteria of Theorem~\ref{thm:adjacency} as given: \url{https://github.com/david44hello/papers_supporting_materials/tree/lee-2026-conjecture-v1.50/lee-2026-conjecture}.} \subjclass[2020]{Primary 52B05; Secondary 06A07, 05C12} \keywords{order polytope, chain polytope, finite poset, graph of a polytope, diameter} \date{} \dedicatory{\normalfont\footnotesize Manuscript version 2.10, November 4, 2026.} \begin{document} \begin{abstract} For a finite poset $P$, Stanley's order polytope $\OP(P)$ and chain polytope $\CP(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 $1$. We show that on connected posets, too, the two diameters can be far apart. For every $k\ge1$ we describe a connected poset $B_k$ with $3k$ elements whose order polytope has graph diameter $k$ and whose chain polytope has graph diameter at most $\lfloor3(k+1)/4\rfloor$; hence the first diameter can exceed the second by any amount. For every $n\ge4$ we construct a connected poset $P_n$ with $2n^2+5n+1$ elements whose order polytope has graph diameter $2$ and whose chain polytope has graph diameter $4$. Finally, for every finite poset $P$, if the graph of $\OP(P)$ has diameter at most $2$, then the graph of $\CP(P)$ has diameter at most $4$; so $2$ is the largest possible difference when the order polytope has graph diameter $2$. \end{abstract} \maketitle \section{Introduction}\label{sec:intro} Let $P$ be a finite poset. An \emph{ideal} of $P$ is a subset that contains, with each of its elements, every smaller element; two distinct elements are \emph{comparable} if one is smaller than the other, and \emph{incomparable} otherwise; an \emph{antichain} is a set of pairwise incomparable elements. The poset $P$ is \emph{connected} if it is nonempty and its comparability graph, in which two elements are joined when they are comparable, is connected. Stanley~\cite{Sta86} associated two polytopes with $P$: the \emph{order polytope} $\OP(P)$, whose vertices are the indicator vectors of the ideals\footnote{Stanley uses filters (up-sets); the map $\xi\mapsto\mathbf 1-\xi$ of $\mathbb R^P$, where $\mathbf 1$ is the all-ones vector, carries Stanley's order polytope onto the one used here, so the two graphs are isomorphic.}, and the \emph{chain polytope} $\CP(P)$, whose vertices are the indicator vectors of the antichains. The \emph{graph} of a polytope has the vertices of the polytope as its vertices and the edges of the polytope as its edges. We call the diameters $\diam\OP(P)$ and $\diam\CP(P)$ of the graphs of $\OP(P)$ and $\CP(P)$ the \emph{order diameter} and the \emph{chain diameter} of $P$. The two polytopes have the same number of vertices (an ideal is determined by the antichain of its maximal elements~\cite{Sta86}), and Hibi, Li, Sahara and Shikama~\cite{HLSS17} proved that their graphs have the same number of edges. Lee~\cite{Lee26} refined this edge theorem and compared further invariants of the two graphs, among them the diameter. Both diameters are additive over disjoint unions of posets, since $\OP(P\sqcup Q)=\OP(P)\times\OP(Q)$ and $\CP(P\sqcup Q)=\CP(P)\times\CP(Q)$, and the graph of a product of polytopes is the Cartesian product of their graphs, in which distances add. Disjoint unions of copies of Lee's small connected posets on which the two diameters differ by $1$, in either direction, therefore give posets with many components on which they differ by any amount \cite[Example~5]{Lee26}. Joining the components by a new least element does not keep such a difference: Lee showed that both diameters are at most $2$ for every poset with a least or a greatest element \cite[Proposition~26]{Lee26}. Indeed, if $P'$ is $P$ with a new least element $\hat0$ adjoined, then every nonempty ideal of $P'$ contains $\hat0$, so $\OP(P')$ is a pyramid over a copy of $\OP(P)$, with apex the indicator vector $0$ of the empty ideal; and $\{\hat0\}$ is the only antichain of $P'$ that contains $\hat0$, so $\CP(P')$ is a pyramid over a copy of $\CP(P)$, with apex the indicator vector of $\{\hat0\}$. The apex of a pyramid is adjacent to every other vertex, so both diameters of $P'$ are at most $2$. The question is therefore how far apart the two diameters can be on a connected poset. On connected posets Lee reports a computer search that found no difference larger than $1$, and states the following conjecture. \begin{conjecture}[{Lee \cite[Conjecture~29]{Lee26}}]\label{conj:lee} For every connected finite poset $P$, \[ \lvert\diam\OP(P)-\diam\CP(P)\rvert\le1. \] \end{conjecture} Versions~2 and~3 of~\cite{Lee26} withdraw the conjecture; version~3 cites an earlier version of~\cite{Goel26}, the expanded version of this paper. We show that both inequalities $\diam\OP(P)-\diam\CP(P)\le1$ and $\diam\CP(P)-\diam\OP(P)\le1$ fail on connected posets, and that no constant can replace~$1$ in the first one. For a connected poset $P$ that is not a chain, both diameters lie between $2$ and the width $w(P)$ \cite[Corollary~25]{Lee26}, where $w(P)$ is the largest size of an antichain; hence they differ by at most $w(P)-2$. Our first family shows that the difference can grow linearly with the width. \needspace{6\baselineskip} \medskip\noindent\textbf{Results} (see also Table~\ref{tab:results})\textbf{.} \begin{itemize}[leftmargin=*] \item The diameter of the graph of $\OP(P)$ can exceed that of $\CP(P)$ by any amount on connected posets: the bands $B_k$ of Definition~\ref{def:band} and Theorem~\ref{thm:main}. This disproves Conjecture~\ref{conj:lee}. \item The diameter of the graph of $\CP(P)$ can exceed that of $\OP(P)$ by $2$ on connected posets: the posets $P_n$, $n\ge4$, of Definition~\ref{rv-def:P} and Theorem~\ref{rv-thm:main}. This disproves Conjecture~\ref{conj:lee} in the other direction; the examples of \cite[Example~5]{Lee26} reach a difference of $1$. \item If $\diam\OP(P)\le2$, then $\diam\CP(P)\le4$, for every finite poset $P$ (Theorem~\ref{rv-thm:upper}). Unlike the bound $\diam\CP(P)\le w(P)$ \cite[Proposition~24]{Lee26}, this bound does not depend on the width. \end{itemize} \begin{table}[ht] \centering\small \caption{Results of this paper and the best results before it.}\label{tab:results} \begin{tabular}{>{\raggedright\arraybackslash}p{0.47\linewidth}>{\raggedright\arraybackslash}p{0.43\linewidth}} \toprule New result & Best result before this paper\\ \midrule $\diam\OP(P)-\diam\CP(P)$ is unbounded on connected posets (Theorem~\ref{thm:main}) & no difference above $1$ in Lee's computer search; at most $w(P)-2$ if $P$ is not a chain (by \cite[Corollary~25]{Lee26})\\\addlinespace $\diam\CP(P)-\diam\OP(P)=2$ for the connected posets $P=P_n$, $n\ge4$ (Theorem~\ref{rv-thm:main}) & difference $1$ \cite[Example~5]{Lee26}\\\addlinespace $\diam\OP(P)\le2$ implies $\diam\CP(P)\le4$ (Theorem~\ref{rv-thm:upper}) & $\diam\CP(P)\le w(P)$ \cite[Proposition~24]{Lee26}\\ \bottomrule \end{tabular} \end{table} \begin{definition}\label{def:band} For $k\ge1$ the \emph{band} $B_k$ is the poset on the $3k$ elements $a_i,b_i,c_i$ $(1\le i\le k)$ whose order is generated by the relations \[ a_ij\}. \] By Lemma~\ref{lem:pairs} the only comparable pairs with one element in $L_j$ and one in $R_j$ are $a_{j-1}