8
$\begingroup$

This is inspired by the recent question Verification of a maximal antichain

The celebrated duality between finite posets and finite distributive lattices has several nice formulations. One of them assigns to a poset $P$ the lattice $\mathscr D\!P$ of its downdeals (I like this word invented, I think, by Freyd). A downdeal of $P$ a subset $D\subseteq P$ satisfying $p\leqslant q\in D$ $\Rightarrow$ $p\in D$. This is a (bounded) distributive lattice with respect to union and intersection operations. Conversely to a finite distributive lattice $L$ one assigns the poset $\Pi\!L$ of its primes. An element $p\in L$ is prime if $x\land y=p$ implies $x=p$ or $y=p$, and primes are ordered by divisibility: $p\leqslant q$ iff $p$ divides $q$, denoted $p|q$ i.e. $\exists x\ q=p\land x$, or equivalently just $p\land q=q$. This seems like an overcomplication in that it reverses the order inherited from $L$, but is just a matter of convenience: you may always switch to all kinds of equivalent definitions, like reversing the order in $P$ or in $L$, replacing primes by join-primes, or passing to complements of downdeals, which are updeals, or both, etc., etc.

The duality says two things. First, that every $L$ can be identified with the lattice of downdeals of its primes, i. e. an element $x\in L$ is uniquely determined by its prime divisors, $D_x:=\{p\in\Pi\!L\mid\exists y\ x=p\land y\}$; in other words, every $x$ is the meet of its prime divisors. Moreover, every downdeal $D$ of $\Pi\!L$ is $D_x$ for a unique $x\in L$, namely, for $x=\bigwedge D$.

Second, the duality says that every poset $P$ can be identified with the poset of primes of $\mathscr D\!P$. Namely, $p\in P$ becomes identified with $\not\uparrow\!\!p:=\{q\in P\mid p\not\leqslant q\}$ and each prime of $\mathscr D\!P$ is $\not\uparrow p$ for a unique $p\in P$. Moreover $p\leqslant q$ iff $\not\uparrow\!\!p\subseteq\not\uparrow\!\!q$.

Now for a finite poset $P$, its downdeals are in one-to-one correspondence with its antichains: to a downdeal $D$ one assigns the antichain $\max\!D$ of its maximal elements, and to an antichain $\alpha\subseteq P$ the downdeal $\downarrow\!\alpha$ of elements below $\alpha$, $\{p\mid\exists\ q\in\alpha\ p\leqslant q\}$.

My question is: can one characterize abstractly, algebraically, without appealing to this duality, those elements of a finite distributive lattice $L$ which correspond to maximal antichains of its dual poset?

More explicitly (I hope I did not make any mistakes when translating it): is there a purely algebraic characterization, without mentioning primes, of those $a\in L$ with the property that for any prime $p\notin D_a$ there is a prime $p'\in\max D_a$ with $p'|p$?

For that inspiring question we actually only need to consider free finite distributive lattices, which means considering only the posets $P$ which are full powersets of some finite set, ordered by inclusion. Not much seems to be known about the cardinality of the set of all maximal antichains in a powerset. According to OEIS, the sequence of these starts like $1,2,3,7,29,376,31746,...$

The question Map on class of all finite posets coming from maximal sized antichains seems to be very closely related, but that one concerns antichains of largest possible size, while mine is about all maximal antichains, i. e. antichains not contained in any other antichain. Clearly such antichains may have various sizes in general, in particular in powersets. For example, both the two element antichain $\{\{1\},\{2\}\}$ and the one element antichain $\{\{1,2\}\}$ are maximal antichains in the powerset of $\{1,2\}$.

$\endgroup$
16
  • 2
    $\begingroup$ Again, this is not really answering your question, and probably you already know this, but there's a very direct way to "see" all the antichains in the distributive lattice $L$: each edge of the Hasse diagram, i.e. each cover relation $x \lessdot y$ can be labeled with the unique join-irreducible $p$ such that $x \vee p = y$. Then the antichain corresponding to a $y \in L$ is the set of labels of edges going down from $y$. I probably did the opposite convention of what you've done everywhere because I like join-irreducibles. $\endgroup$ Jan 26, 2021 at 15:44
  • 2
    $\begingroup$ Sorry to keep clogging up your comments, but here's another perspective: the nontrivial fact about the elements corresponding to maximum sized antichains of $P$ in the distributive $L=J(P)$ is that they form a sublattice. One could ask if there are any interesting lattice properties of the maximal (as opposed to maximum sized) antichains. $\endgroup$ Jan 26, 2021 at 15:57
  • 5
    $\begingroup$ The maximal antichains $A$ of $P$ are in bijection with the maximal intervals $[x,y]$ of $L$ that are boolean algebras. (That is, $[x,y]$ is not contained in a larger interval that is a boolean algebra.) The size of $A$ is the length of $[x,y]$. If the element $y$ corresponds to the downdeal (I prefer the term "order ideal") $I$, then $A$ is the set of maximal elements of $I$. $\endgroup$ Jan 26, 2021 at 15:59
  • 2
    $\begingroup$ @SamHopkins, yes they form a sublattice. I'm currently looking for a good reference. $\endgroup$ Jan 26, 2021 at 18:52
  • 2
    $\begingroup$ I admit that I did not check that the order relation is the same, but if it is, the reference is Reuter, Klaus. "The jump number and the lattice of maximal antichains." Discrete Mathematics 88.2-3 (1991): 289-307. $\endgroup$ Jan 26, 2021 at 19:02

1 Answer 1

0
$\begingroup$

This is a (community wiki) description of a possible answer, rather than the answer itself. Everybody is invited to try and turn this into a real answer. Or (obviously) abandon it and write the really real answer.

Richard Stanley explains in a comment that the maximal antichains $A$ of $P$ are in one-to-one correspondence with maximal boolean intervals of $\mathscr D\!P$.

In general, given $D'\subseteq D$ with $D,D'\in\mathscr D\!P$, it is easy to see that the interval $[D',D]$ is lattice isomorphic to $\mathscr D(D\setminus D')$, where $D\setminus D'$ is the subposet of $P$ with the induced partial order. So $[D',D]$ is boolean if and only if $D\setminus D'$ is an antichain.

Conversely, any antichain $A\subseteq P$ gives rise to such boolean interval, with $D=\downarrow\!A$ and $D'=D\setminus A$. And (clearly?) maximal antichains correspond to maximal boolean intervals.

Now there is a construction, which I have first seen performed by Harold Simmons. For an element $a$ in any complete Heyting algebra, let $$ \tau a=\bigwedge\{b\geqslant a\mid b\to a=a\}. $$ Then $[a,\tau a]$ is the largest boolean interval with bottom $a$.

Clearly in a complete co-Heyting algebra there is a dually defined operator $\delta$ such that $[\delta b,b]$ is the largest boolean interval with top $b$.

Example. In the lattice of closed sets of a topological space, $\delta$ is the Cantor-Bendixson derivative. That is, for a closed set $C$, $\delta C$ is the set of its limit points.

So if we are in a complete bi-Heyting algebra, both operators are available, and an interval $[a,b]$ is maximal boolean if and only if $a=\delta b$ and $b=\tau a$.

This then seemingly implies that both elements $a$ satisfying $\delta\tau a=a$ and elements $b$ satisfying $\tau\delta b=b$ should somehow correspond to maximal antichains. Specifically, in the case when our algebra is $\mathscr D\!P$ for some poset $P$, then $\tau\delta D=D$ for $D\in\mathscr D\!P$ should mean that $\max D$ is a maximal antichain, while $\delta\tau D=D$ should mean that $\min(P\setminus D)$ is a maximal antichain.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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