## Orbits of antichains in ranked posets.(English)Zbl 0777.06002

The author considers a permutation $$f$$ of antichains in a poset $$P$$. The operation $$f$$ can also be viewed in terms of monotone Boolean functions on $$P$$; namely, for an antichain $$A$$ in $$P$$, $$f(A)$$ is the set of upper zeros of the monotone Boolean function having $$A$$ as the set of lower units. The operation $$f$$ has been extensively studied in the case where $$P$$ is the lattice of subsets of a finite set $$\Omega$$, and the following conjectures were formulated by M. Deza and K. Fukuda [Coding Theory and Design Theory, Part II, IMA Vol. Math. Appl. 21, 72-92 (1990; Zbl 0723.05114)]:
(a) If $$A\subseteq P_ k(\Omega)$$ (i.e. $$A$$ is the set of $$k$$-element subsets of $$\Omega$$), and $$B=f^ n(A)\subseteq P_ 1(\Omega)$$, then $$P_ k(\Omega)\backslash A=f^{n+1-k}(P_ 1(\Omega)\backslash B)$$.
(b) If $$A\subseteq P_ k(\Omega)$$, $$B=P_ k(\Omega)\backslash A$$ and $$(A,A_ 1,\dots,A_{n-1})$$, $$(B,B_ 1,\dots,B_{m-1})$$ are cycles of the permutation $$f$$, then $$n=m$$ and $$| A|+| A_ 1|+\cdots+| A_{n-1}|=| B|+| B_ 1|+\cdots+| B_{m-1}|$$.
Regarding these conjectures, Theorem 1 below is established for ranked posets $$P$$, where a ranked poset is defined as follows:
$$P$$ is a ranked poset of height $$r$$ if there exists a function $$rk: P\to\{0,1,\dots,r\}$$ such that (a) $$rk(x)=0$$ iff $$x \uparrow=\emptyset$$; $$(x \uparrow=\{y\in P$$; $$y>x$$ and there is no $$z$$ such that $$y>z>x\})$$, (b) $$rk(x)=r$$ iff $$x \downarrow=\emptyset$$; $$(x \downarrow=\{y\in P$$; $$y<x$$ and there is no $$z$$ such that $$y<z<x\})$$, (c) if $$y\in x \uparrow$$ then $$rk(y)=rk(x)+1$$.
Theorem 1: Let $$P$$ be a ranked poset and let $$A\subseteq P_ a$$ (the $$a$$th layer of $$P$$). (a) If $$B=f^ k(A)\subseteq P_ b$$, then $$P_ a\backslash A=f^{k+b-a}(P_ b\backslash B)$$. (b) If $$(A,A_ 1,\dots,A_{n-1})$$ and $$(P_ a\backslash A, X_ 1,\dots,X_{m-1})$$ are cycles of the permutation $$f$$, then $$n=m$$ and any element of $$P$$ is contained in the same number of antichains from both cycles. In particular, $$| A|+| A_ 1|+\cdots+| A_{n- 1}|=| P_ a\backslash A|+| X_ 1|+\cdots+| X_{m-1}|$$.
In another main result (Theorem 2) the author considers orbits of antichains in a direct product of two chains. It turns out that in this case all possible orbit lengths can be determined.
Theorem 2: If $$P$$ is a direct product of two chains of orders $$n$$ and $$m$$, then the length of any orbit of the permutation $$f$$ is $$(n+m)/d$$ for some $$d$$ dividing both $$n$$ and $$m$$. Any number of this form is the length of some orbit.
Reviewer: M.Höft (Dearborn)

### MSC:

 06A06 Partial orders, general 06E30 Boolean functions

Zbl 0723.05114
Full Text: