Posets with the Same Number of Order Ideals of Each Cardinality: a problem from Stanley's ``Enumerative Combinatorics''
by
Jonathan David Farley
Department of Mathematics, Vanderbilt 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 <= 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 N, let f_k(n) be the number of non-isomorphic posets P such that, if 1 <= i <= n-1, then P has exactly k order ideals of cardinality i.

In ``Enumerative Combinatorics'' (the classic 1986 text of the MIT 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.

We also discuss the 2000 U.S. presidential elections.

Date received: May 11, 2001