一道有趣组合题

Intersecting family

Posted by ethan-zhou on November 14, 2024

组合学课作业里的一题,手玩了好久才想出来,记录一下。

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
本文为作者原创,转载请注明出处:本文链接


阅读量:


icon