Let $P$ be a finite poset. Let $\mathcal{A}$ denote the set of antichains of $P$. Equip $\mathcal{A}$ with a partial order $\preceq$ whereby $X \preceq Y$ means for all $x \in X$ there exists $y \in Y$ such that $x \leq_P y$. Then it is easy to see that $(\mathcal{A},\preceq)$ is isomorphic to $J(P)$, the distributive lattice of order ideals of $P$ (just send an antichain to the order ideal it generates).

Let $\mathcal{A}_{\mathrm{max}} := \{A \in \mathcal{A}\colon \forall_{B\in\mathcal{A}}\#B\le\#A\}$. Then it is known that $\mathcal{A}_{\mathrm{max}}$ is a sublattice of $\mathcal{A}$ with respect to the partial order $\preceq$ (see the paper of Freese linked to below). In particular, $\mathcal{A}_{\mathrm{max}}$ is a distributive lattice, and hence by Birkhoff's Fundamental Theorem of Finite Distributive Lattices, has the form $\mathcal{A}_{\mathrm{max}}=J(P')$ for some other (unique up to isomorphism) finite poset $P'$, namely the induced subposet of join-irreducible elements.

The map $P \mapsto P'$ defines a self-map on the class of all finite posets. This map is far from injective: for instance any poset with a unique antichain of maximal cardinality (for instance $P=n\underline{\mathbf{1}}$ an antichain) is sent to the empty poset. On the other hand, for $P=\underline{\mathbf{n}}$ a chain, we have $P' = \underline{\mathbf{n-1}}$. Also, experimentally it seems that with $P = \underline{\mathbf{a}} \times \underline{\mathbf{b}}$ a product of chains, with $a \geq b$, we have $P' = \underline{\mathbf{a-b}} \times \underline{\mathbf{b}}$. (And it looks like similar behavior may propagate to product of three chains and beyond.)

Broad question: How can this map $P \mapsto P'$ be understood? Is there a "simpler" description than the one I have given? Are there other families of posets on which it exhibits interesting behavior? (EDIT: Other questions along these lines: Is the map surjective?, Is $P'$ always isomorphic to a subposet of $P$?, et cetera.)

Specific question: Is it true that this map has $\underline{\mathbf{a}} \times \underline{\mathbf{b}} \mapsto \underline{\mathbf{a-b}} \times \underline{\mathbf{b}}$? What about products of many chains?

Freese, Ralph, An application of Dilworth’s lattice of maximal antichains, Discrete Math. 7, 107-109 (1974). ZBL0271.05011.

  • 4
    $\begingroup$ In her Ph.D. thesis at dspace.mit.edu/handle/1721.1/104603?show=full, Efrat Engel computes $P'$ for some posets $P$. Also, the surjectivity of the map $P\to P'$ follows from Exercise 3.72(b) of EC1. $\endgroup$ Nov 25 '19 at 20:10
  • $\begingroup$ @RichardStanley: Thanks for these great references! $\endgroup$ Nov 25 '19 at 20:16
  • $\begingroup$ (I realized the question about fixed points was silly: unless $P$ is empty, of course $J(P)$ will be strictly bigger than $\mathcal{A}_{\mathrm{max}} \subseteq J(P)$ because $J(P)$ has the emptyset, but $\mathcal{A}_{\mathrm{max}}$ won't.) $\endgroup$ Nov 26 '19 at 1:06

The references given by Richard Stanley answer most of my array of questions.

In particular, Koh showed that the map $P \mapsto P'$ is surjective in "On the lattice of maximum-sized antichains of a finite poset", and gave some more information about the fibers of this map in "Maximum-sized antichains in minimal posets" (both linked below).

Also, in Engel's MIT PhD thesis (available online), she computes $P'$ for various posets $P$, including the case of the product of three chains; she describes (in Section 3.3) the distributive lattice in question as the lattice of Semistandard Young Tableaux of rectangular shape $c^r$ with entries at most $n$ with coordinate-wise order, but it is easy to see that this is the same as $J(\underline{\mathbf{c}} \times \underline{\mathbf{r}}\times\underline{\mathbf{n-r}})$. (Note that she views the map in question as being of the form $J(P)\to J(P')$, but of course by the Fundamental Theorem of Finite Distributive Lattices, this is no different than $P\to P'$.)

Koh, K. M., Maximum-sized antichains in minimal posets, Algebra Univers. 20, 217-228 (1985). ZBL0602.06001.described some

Koh, K. M., On the lattice of maximum-sized antichains of a finite poset, Algebra Univers. 17, 73-86 (1983). ZBL0524.06003.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.