On cloud-antichains and related configurations
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.
- A Sperner theorem on unrelated chains of subsets
- An identity in combinatorial extremal theory
- An inequality for the weights of two families of sets, their unions and intersections
- Convex hulls of more-part Sperner families
- scientific article; zbMATH DE number 3636041 (Why is no real title available?)
- On a lemma of Littlewood and Offord
- On generalized graphs
- A generalization of the AZ identity
- The maximal length of cloud-antichains
- Pseudo-LYM inequalities and AZ identities
- Towards characterizing equality in correlation inequalities
- Optimal pairs of incomparable clouds in multisets
- On colorings of the Boolean lattice avoiding a rainbow copy of a poset
- AZ-identities and strict 2-part Sperner properties of product posets
- Disjoint systems
- Minimising the total number of subsets and supersets
- Bollobás set pair inequalities for compositions
This page was built for publication: On cloud-antichains and related configurations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757448)
