On cloud-antichains and related configurations (Q757448)

Given a poset P, a cloud-antichain (CAC) \((B_ i)^ N_{i=1}\) of length N in P is a family of subsets \(B_ i\) of P such that for distinct indices i and j, if \(x\in B_ i\), \(y\in B_ j\), then x and y are not comparable. If \(| B_ i| =1\), for all i, then \((B_ i)^ N_{i=1}\) is an antichain of length N. The sets \(B_ i\) are called clouds. If \(| B_ i| =k\) for all i, then \((B_ i)^ N_{i=1}\) is a k-cloud-antichain (k-CAC). Similarly, \((C_ i)^ N_{i=1}\) is a cloud-chain (CC) of length M in P if \(C_ i\) is a subset of P and if for distinct indices \(i<j\), \(x\in C_ i\), \(y\in C_ j\) implies \(x<y.\) If P is the power set of \(\Omega =\{1,...,n\}\) then these notions can be used to improve and tighten previous results. For example the well-known Bolloba's inequality becomes an identity. The uniqueness in the Sperner Theorem for unrelated chains of subsets is also obtained as a consequence. If \(N=2\), then it is shown that \(\min \{| B_ 1|,| B_ 2| \}\leq 2^{n-2}\), \(| B_ 1| | B_ 2| \leq 2^{2n-4}\) and these bounds are tight. Based on the nature of the arguments used to obtain these results the authors also consider mutually interesting systems (MIS) (A,B), A,B\(\leq P\), \(a\cap b\neq \emptyset\) for \(a\in A\), \(b\in B\), and mutually comparable systems (MCS) (A,B), A,B\(\subseteq P\) such that \(a\in A\), \(b\in B\) implies \(a\subset b\) or \(b\subset a\). For the ranges of triples (\(| A|,| B|,| A\cap B|)\) of cardinalities asymptotically optimal results are obtained for MIS's and exact results for MCS's. The results obtained are interesting and they appear to be of possible use in a variety of applications. For example, in the study of parallelism opportunities in computer architectures such as the n-cube (i.e., P) the concept of a cloud-antichain seems to be a useful notion, while some of the parameters obtained could be meaningful in coming up with complexity estimates for various situations encountered there.