12
$\begingroup$

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.

$\endgroup$
5
  • 8
    $\begingroup$ The bijection $L_X$ is well-known and appears in many papers. (You seem to be using $L_X$ in two different ways.) It has been called the Fon-der-Flaass action, the Panyushev action, and rowmotion. One reference is arxiv.org/pdf/1108.1172v3.pdf. However, I don't know of any work directly relevant to the question here. $\endgroup$ May 21, 2015 at 2:02
  • $\begingroup$ A quick note: If we take $n_1+1$, $n_2+1$, ... to be the first block of primes $2$, $3$, $5$, ..., $p$, chosen to have sum as close as possible to $n$, then $p \approx \sqrt{n \log n}$ and $LCM(2,3,\ldots, p) \approx e^p \approx \exp(\sqrt{n \log n})$. So we are trying to separate an $\exp(cn)$ upper bound and an $\exp(n^{1/2+\epsilon})$ lower bound. $\endgroup$ May 21, 2015 at 18:49
  • 1
    $\begingroup$ Readers of my previous comment should realize that what I call $L_X$ has been changed in the question to $Q_X$. $\endgroup$ May 22, 2015 at 0:03
  • $\begingroup$ Do you have better than $|X|+1$ for connected $X$? $\endgroup$
    – domotorp
    May 22, 2015 at 7:31
  • $\begingroup$ domotorp. For a simple connected example better than $|X|+1$, take the tree $X=\{0,00,000,01,011,0111\}$ ordered by extension of strings, then the cycle in $\mathcal{A}_{X}$ containing $\emptyset$ has length 13. $\endgroup$ May 22, 2015 at 17:09

1 Answer 1

2
$\begingroup$

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.Order 15 poset.

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

$\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.