Orbits of antichains in ranked posets (Q1209286)

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 \textit{M. Deza} and \textit{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.