How long can a cycle of antichains in a finite partial order be?

Question

Suppose that $X$ is a finite partially ordered set. Then a subset $A\subseteq X$ is said to be an antichain if there do not exist elements $a,b\in A$ with $a<b$. Let $\mathcal{A}_{X}$ be the set of all antichains in $X$. Let $L_{X}$ be the collection of all downwards closed subsets of $X$ and let $U_{X}$ be the collection of all upwards closed subsets of $X$. Then

Let $\mathfrak{l}_{X}:\mathcal{A}_{X}\rightarrow L_{X}$ be the mapping where $\mathfrak{l}_{X}(A)=\{x\in X|\exists a\in A,x\leq a\}$ and let $\mathfrak{u}_{X}:\mathcal{A}_{X}\rightarrow U_{X}$ be the mapping where $\mathfrak{u}_{X}(A)=\{x\in X|\exists a\in A,x\geq a\}$. The the mappings $\mathfrak{l}_{X},\mathfrak{u}_{X}$ are bijections.

Define a mapping $Q_{X}:\mathcal{A}_{X}\rightarrow\mathcal{A}_{X}$ by letting $Q_{X}(A)= \mathfrak{u}_{X}^{-1}(\mathfrak{l}_{X}(A)^{c})$ for each antichain $A$. Then $Q_{X}$ is a bijection from $\mathcal{A}_{X}$ to $\mathcal{A}_{X}$, so since $Q_{X}$ is a permutation of $\mathcal{A}_{X}$, $Q_{X}$ is a composition of disjoint cycles.

If $n$ is a natural number, then let $t_{n}$ be the largest number such that there is a poset $X$ with $|X|=n$ and the permutation $Q_{X}$ has a cycle of length $t_{n}$.

I doubt that there is a nice explicit formula for $t_{n}$, but it seems like one can produce decent upper and lower bounds for $t_{n}$ or limits involving $t_{n}$. What are some good upper and lower bounds or limits for the value of $t_{n}$?

It is obvious that $t_{n}\leq 2^{n}$ since if $|X|=n$, the $|\mathcal{A}_{X}|\leq 2^{n}$. Furthermore, if $n>1$, then $t_{n}<2^{n}$ since if $t_{n}=2^{n}$ and $\mathcal{A}_{X}$ has a cycle of length $2^{n}$, then $\mathcal{A}_{X}=P(X)$, so $X\in\mathcal{A}_{X}$. However, this implies that $\mathcal{A}_{X}$ does not have a cycle of length $2^{n}$, a contradiction. One can use a similar but more complicated argument to get more precise upper bounds for $t_{n}$.

Now suppose that $n_{1},...,n_{k}$ are natural numbers. Then let $X$ be the partially ordered set of cardinality $n_{1}+...+n_{k}$ with $k$ connected components and where the $i$-th connected component of $X$ is a chain of length $n_{i}$.

Then each cycle in $\mathcal{A}_{X}$ has length $\textrm{Lcm}(n_{1}+1,...,n_{k}+1)$, so $t_{n_{1}+...+n_{k}}\geq\textrm{Lcm}(n_{1}+1,...,n_{k}+1)$. Therefore, for example $t_{15}\geq\textrm{Lcm}(3,4,5,7)=840$. This however is only a rough lower bound and I am sure that this lower bound can be improved significantly.

Answer 1

Let us consider the slightly more restrictive problem of finding the longest cycle of antichains that start with the empty antichain. Let $\textrm{orb}(P)$ be the cycle of antichains of poset $P$ starting with the empty antichain.

We denote the disjoint union of posets $P$ and $Q$ as $P+Q$. Let the ordinal sum $P\oplus Q$ be the poset $P$ stacked on top of $Q$. So for $x,y \in P\cup Q$ we have $x<y$ in $P\oplus Q$ if and only if either of the following three statements holds:

1. $x,y\in P$ and $x<y$ in $P$.
2. $x,y\in Q$ and $x<y$ in $Q$.
3. $x\in Q$ and $y \in P$.

Now we can see that $|\textrm{orb}(P\oplus Q)| = |\textrm{orb}(P)| + |\textrm{orb}(Q)| - 1$ and $|\textrm{orb}(P+Q)|=\textrm{lcm}(|\textrm{orb}(P)|,|\textrm{orb}(Q)|)$. So starting with $P_0 = \bf{1}$ (the poset with one element) we can define $P_n=(P_0+\cdots|P_{n-1})\oplus \bf{1}$. Thus $P_i$ has $2^i$ elements, and for $i\ne j$, $|\mathrm{orb(P_i)}|$ is relatively prime to $|\mathrm{orb(P_j)}|$. It is easy to see that $|\mathrm{orb(P_i)}|$ grows faster that $2^{i/2}$ (in fact it grows as $\alpha^i$ where $\alpha \approx 1.59791021803187$). This allows us to make posets of any size $n$ by taking the disjoint union of $P_i$ corresponding to the binary representation of $n$, and the disjoint union will have orbit size greater than $\alpha^n$.

Here are the first four steps of the construction..

This is not optimal. There are non series-parallel posets on 8 elements having orbit length 50, while this construction gives 43.