A Sperner-type theorem and qualitative independence (Q1185884): Difference between revisions

The following theorem is proved: Let \(M(n)\) denote the cardinality of the largest family \(\{C_ i\}^{M(n)}_{i=1}\) of subsets of an \(n\)-element set with the property that for an appropriate bipartition of every \(C_ i\), \(C_ i=A_ i\cup B_ i\), \(A_ i\cap B_ i=\emptyset\), one has \(A_ i\not\subset C_ j\), \(B_ i\not\subset C_ j\) for \(j\neq i\). Then \(\lim_{n\to\infty}[M(n)]^{1/n}={1+\sqrt 5\over 2}\). The construction is used to improve the lower bound on the number of qualitatively independent 3-partitions of an \(n\)-set of \textit{S. Poljak} and \textit{Z. Tuza} [J. Comb. Theory, Ser. A 51, 111-116 (1989; Zbl 0675.05005)]. Finally the connection to a class of zero-error capacity problems in information theory is discussed.