= Solution
Assume no deletion works. For each $x\in A_i$, some $A_j$ contains $A_i\setminus\{x\}$; otherwise deleting $x$ preserves the <antichain>. For different deleted elements these witnesses are distinct, since one witness containing both complements would contain $A_i$. Thus every element of $A_i$ belongs to at least $|A_i|$ sets.
Use the incidence graph with left class $\bigcup_iA_i$ and right class $\{A_i\}$. Along every incidence edge, the degree of the element is at least the degree $|A_i|$ of the set vertex. Part (b) gives a matching from the union into the $k$ sets, forcing $|\bigcup_iA_i|\le k$, a contradiction.
Back to article page
