组合学课作业里的一题，手玩了好久才想出来，记录一下。
3. Prove that for any intersecting family $\mathcal{F} \subset 2^{[n]}$, there exists an intersecting family $\mathcal{F}’ \subset 2^{[n]}$ satisfying that $|\mathcal{F}’| = 2^{n-1}$ and $\mathcal{F} \subset \mathcal{F}’$.
Proof: We show how to expand $\mathcal{F}$ to an intersecting family of size $2^{n-1}$.
Definition: $\operatorname{expand}(\mathcal{F}) := {S \mid \exists U \in \mathcal{F}, U \subseteq S}$, $\operatorname{ban}(\mathcal{F}) := {S \mid \exists U \in \mathcal{F}, S = \overline{U} }$. We call a family fully expanded if $\operatorname{expand}(\mathcal{F}) = \mathcal{F}$.
Lemma: If $\mathcal{F}$ is a fully expanded intersecting family, then $\forall S \not\in \operatorname{ban}(\mathcal{F})$, $S$ intersects with all sets in $\mathcal{F}$.
Assume $S$ does not intersect with $U \in \mathcal{F}$, then $U \subseteq \overline{S}$, which contradicts the fully expanded property.
Lemma: $|\operatorname{ban}(\mathcal{F})| = |\mathcal{F}|$.
With the above auxiliary lemmas, we can give a construction of the desired family. Let $\mathcal{F}’ = \operatorname{expand}(\mathcal{F})$. While $|\mathcal{F’}| < 2^{n-1}$, we can always find the maximal set $S$ such that $S \not\in \mathcal{F’}$ and $S \not\in \operatorname{ban}(\mathcal{F’})$ (because $|\mathcal{F}| + |\operatorname{ban}(\mathcal{F})| < 2^n$) and add it into $\mathcal{F}’ \gets \mathcal{F}’ \cup {S}$. The new $\mathcal{F}’$ is still fully expanded, and its size is increased by 1.
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: