数学の命題示しました

主に組合せ論について，読んだ本で出てきたことや，考えたことを書きます．

2018-05-23

交差族のサイズの上限

『現代組合せ論』Peter Frankl, 秋山仁

定理 1.1

$X\triangleq \{1,2,\ldots,n\}, \mathcal{F}\subseteq 2^{X}$ とする.
任意の $F,F'\in \mathcal{F}$ に対し $F\cap F'\neq\emptyset$ を満たすならば
$|\mathcal{F}|\leq 2^{n-1}$ である.