Orbits of antichains in ranked posets
type: Item
instance of: scholarly article
title: Orbits of antichains in ranked posets
zbMATH Open document ID: 0777.06002
published in: European Journal of Combinatorics
publication date: 1993-05-16T00:00:00Z
review text: 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 …
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06E30
zbMATH DE Number: 167691
zbMATH Keywords: permutation of antichains in a poset
zbMATH Keywords: monotone Boolean functions
zbMATH Keywords: ranked poset
zbMATH Keywords: orbits of antichains in a direct product of two chains
zbMATH Keywords: possible orbit lengths
author: Dmitry G. Fon-Der-Flaass
MaRDI profile type: Publication
full work available at URL: eujc.1993.1003
OpenAlex ID: W1977467370
DOI: 10.1006/EUJC.1993.1003
description: scientific article; zbMATH DE number 167691