On the Gap of Finite Posets

Abstract

Let $P$ be a finite nonempty poset with $n$ elements, let $f:P\to \{1,\dots ,n\}$ be a uniformly random order-preserving bijection, and put $h_P(x)=\mathbb{E}[f(x)]$. Aires and Kahn (2025) introduced $\mathrm{gap}(P)$ as the largest difference between consecutive values in the ordered list consisting of $0$, $n+1$, and all the expected ranks $h_P(x)$. Write $w(P)$ for the largest size of a pairwise incomparable subset. We prove three results. First, we prove a weighted strengthening of an ideal inequality conjectured by Kahn and obtain the explicit gap-width bound $\mathrm{gap}(P)\le 2w(P)-1$. Second, for every $L>0$ we construct a width-two poset such that the expected-rank list of every maximal chain has a gap of at least $L$, with $0$ and $|P|+1$ added as endpoints. Finally, for every $r\in \mathbb{N}$, we construct a poset $P_r$ for which the relative order induced on every nonempty selected set $X$ has base-two entropy below $3|X|$, while $\mathrm{gap}(P_r)\ge (3/2{)}^r$. Thus the gap can be arbitrarily large while the induced order on every selected set has relatively small entropy. The key ideas behind all three results were found by ChatGPT 5.6 Sol.

25 pages, 4 figures