Orbits of antichains in ranked posets (Q1209286): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Dmitry G. Fon-Der-Flaass / rank | |||
Property / author | |||
Property / author: Dmitry G. Fon-Der-Flaass / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/eujc.1993.1003 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1977467370 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 18:42, 21 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Orbits of antichains in ranked posets |
scientific article |
Statements
Orbits of antichains in ranked posets (English)
0 references
16 May 1993
0 references
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.
0 references
permutation of antichains in a poset
0 references
monotone Boolean functions
0 references
ranked poset
0 references
orbits of antichains in a direct product of two chains
0 references
possible orbit lengths
0 references