Let $X$ be a finite set with $|X| =n $ and $\mathcal{A} \subset \mathcal{P}(X)$ a set system.

Call $\mathcal{A}$ a cross-cut if $\forall B \in \mathcal{P}(X), \; \exists A \in \mathcal{A} $ such that $A \subset B $ or $B \subset A$

I am asked to show that any cross-cut $\mathcal{A}$ contains a cross-cut that has size at most ${n}\choose{\lfloor \frac{n}{2}\rfloor}$.

My thoughts are that this can be achieved by taking a minimal cross-cut $\mathcal{B}$ contained in $\mathcal{A}$. Then, by minimality, for every $B \in \mathcal{B}$, we have that:

$\exists C \in \mathcal{P}(X),\; \forall A \in \mathcal{B} - \{B\}$ such that $A \not\subset C$ and $C \not\subset A$

Then taking such a $C$, we can consider $(\mathcal{B} \cup C) - \{B\}$. Thinking about graphs where two sets are adjacent if one is contained in the other, then we see $(\mathcal{B} \cup C) - \{B\}$ has one less edge than $\mathcal{B}$.

Now, I want to continue and keep switching out sets of $\mathcal{B}$ until we get $\mathcal{C}$ which is an anti-chain, then we are done by Sperner.

However, there is no guarantee that $\mathcal{B} \cup C - \{B\}$ is contained in $\mathcal{A}$, so even if it were a cross-cut, there is no guarantee it is "minimal".

I am stuck at this point and I think that perhaps I am supposed to turn this sub-cross-cut $\mathcal{B}$ into an anti-chain in some other way, but I'm not entirely sure how that might be achieved.

  • $\begingroup$ @greedoid it is a subset of the power set, sorry for the mistake. n is the size of $X$. I've made the appropriate edits. $\endgroup$ – user366818 Oct 28 '18 at 15:28
  • $\begingroup$ Asked at math.stackexchange.com/questions/353249/… but not answered $\endgroup$ – Dap Feb 10 at 6:32

Hint 1: there are minimal cross cuts that are not antichains, so you are right that you need a modification to get an antichain.

Example for hint 1:

Take $X=\mathbb Z/5\mathbb Z$ and the ten-element set family consisting of pairs $\{i,i+1\}$ and triples $\{i,i+1,i+2\}$ for each $i\in X.$

Hint 2:

The set of inclusion-minimal elements of a set family is always an antichain, so you just need to modify the other elements.


Assume $\mathcal A$ is a minimal cross cut. Let $\mathcal A_0$ be the set of inclusion-minimal elements of $\mathcal A.$ For each $A\in\mathcal A\setminus\mathcal A_0$ pick a set $W_A\subset A$ such that for all $B\in\mathcal A\setminus\{A\}$ we have $W_A\not\subset B$ and $B\not\subset W_A.$ Let $\mathcal W=\{W_A\mid A\in \mathcal A\setminus\mathcal A_0\}.$ Then $\mathcal A_0\cup\mathcal W$ is an antichain and has the same order as $\mathcal A.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.