# Question on cross-cuts contained in cross-cuts

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.

• @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. – user366818 Oct 28 '18 at 15:28
• Asked at math.stackexchange.com/questions/353249/… but not answered – 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.

Solution:

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.$$