Optimal pairs of incomparable clouds in multisets (Q1915140): Difference between revisions

Let \(k^n\) be the \(n\)th product of \(n\)-element chains. Two sets \(A,B \subset k^n\) are incomparable if \(a \nleq b\), \(a \ngeq b\) for all \(a \in A\), \(b \in B\). Let \(f_n (\alpha) = \max \{|B |: A, B \subset k^n\) with \(|A |= \alpha\) and \(A\) incomparable to \(B\}\). The authors are concerned with the growth of the function \(f_n\) and prove, for example, the recursion: for every \(\alpha\), \(0 \leq \alpha \leq k^{n - 2}\) and for \(s \geq 0\): \[ f_n (\alpha) = (k - 1)k^{n - 1} + kf_{n - 2} (\alpha) - (k - 1) \alpha, \] \[ f_{n + 2s} (\alpha) = (k^s - 1) ( k^{n + s} - \alpha) + k^s f_n (\alpha). \] In the case \(k = 2\) these results are improvements of earlier ones by \textit{R. Ahlswede} and \textit{Z. Zhang} [Discrete Math. 85, 225-245 (1990; Zbl 0723.06001)].