On disjoint chains of subsets
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.
- A new matching property for posets and existence of disjoint chains
- Long symmetric chains in the Boolean lattice
- An o(n) monotonicity tester for Boolean functions over the hypercube
- Nested chain order
- INCLUSION THEOREMS FOR SUBSETS
- Monotonicity testing and shortest-path routing on the cube
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Erasure-Resilient Property Testing
- Parameterized property testing of functions
- Optimal unateness testers for real-valued functions: adaptivity helps
- Approximating the distance to monotonicity of Boolean functions
- Two proofs of Bondy's theorem on induced subsets and two related questions
- Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
- Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
- Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
- Nearly optimal bounds for sample-based testing and learning of k-monotone functions
- Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron (extended abstract)
- A \(d^{1/2+o(1)}\) monotonicity tester for Boolean functions on \(d\)-dimensional hypergrids
- Directed hypercube routing, a generalized Lehman-Ron theorem, and monotonicity testing
This page was built for publication: On disjoint chains of subsets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5937251)