Problem involving set systems - combinatorics.

313 Views Asked by At

The question is as follows:

$A \subset \mathbb{P}(X)$ is called a cross-cut if for every $B \subset X$ there exists $A' \in A$ with $B \subset A'$ or $A' \subset B$. Prove that every cross-cut contains a cross-cut of size at most $n \choose \lfloor{n/2}\rfloor$.

I expect the solution is very short once you have the right idea, but I cannot think how to start. I'm not sure how to best identify redundancy in such a construction.

Any ideas? It follows a chapter on Sperner's lemma, and other similar results.