Posets with the Same Number of Order Ideals of Each Cardinality: a problem from Stanley's "Enumerative Combinatorics"

Jonathan Farley
Fulbright Distinguished Scholar, Oxford University


Let $P$ be an n-element partially ordered set (poset). A subset $I$ is an "order ideal" if, for all $i\in I$ and $p\in P$, if $p\le i$ then $p\in I$. The collection of all order ideals, partially ordered by inclusion, is closed under unions and intersections, and hence forms a "distributive lattice."

For $k\in\Bbb N$, let $f_k(n)$ be the number of non-isomorphic posets $P$ such that, if $1\le i\le n-1$, then $P$ has exactly $k$ order ideals of cardinality $i$.

In "Enumerative Combinatorics" (the classic 1986 text of the Massachusetts Institute of Technology combinatorialist Richard P. Stanley), an unsolved problem is to determine the generating function for $f_k(n)$. Due to an observation of Paul Edelman, it suffices to consider the case $k=3$.

We determine the all the posets with the prescribed property, by considering their corresponding distributive lattices. We use a result of the author and Stefan E. Schmidt (obtained in response to another issue raised by Stanley concerning group actions on posets) which says whether or not a poset is isomorphic to a distributive lattice if all of its rank 3 intervals are.

Finally, we show how these results can be used to solve a problem of Ivo Rosenberg, dating back to the 1981 Banff Conference on Ordered Sets.