On disjoint chains of subsets (Q5937251)

In this note the authors prove the following theorem. Given a family \(\mathcal{S}\) of \(m\) \(s\)-element subsets of \(\{1,2,\ldots,n\}\) and a family \(\mathcal{R}\) of \(m\) \(r\)-element subsets of \(\{1,2,\ldots,n\}\), with \(r<s\), and given a bijection \(\phi: \mathcal{S}\rightarrow\mathcal{R}\) satisfying \(\phi(A)\subset A\) for each \(A\in\mathcal{S}\), there exist \(m\) disjoint saturated chains in the Boolean algebra on \(\{1,2,\ldots,n\}\) that contain all the subsets in \(\mathcal{S}\) and \(\mathcal{R}\). This theorem already appeared in \textit{O. Goldreich}, \textit{S. Goldwasser}, \textit{E. Lehman}, and \textit{D. Ron} [``Testing monotonicity'', in: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 426-435 (1998)], with the same proof as is presented here. The proof is by induction on \(m\) and \(s-r\), and uses Menger's Theorem. The disjoint saturated chains cannot always be chosen to refine the chains \(\phi(A)\subset A\); an example is given to show this.