B1.5

Combinatorics | Part II, 2001

Let A⊂[n](r)\mathcal{A} \subset[n]^{(r)} where r⩽n/2r \leqslant n / 2. Prove that, if A\mathcal{A} is 1-intersecting, then ∣A∣⩽(n−1r−1)|\mathcal{A}| \leqslant\left(\begin{array}{l}n-1 \\ r-1\end{array}\right). State an upper bound on ∣A∣|\mathcal{A}| that is valid if A\mathcal{A} is tt-intersecting and nn is large compared to rr and tt.

Let B⊂P([n])\mathcal{B} \subset \mathcal{P}([n]) be maximal 1-intersecting; that is, B\mathcal{B} is 1-intersecting but if B⊂C⊂P([n])\mathcal{B} \subset \mathcal{C} \subset \mathcal{P}([n]) and B≠C\mathcal{B} \neq \mathcal{C} then C\mathcal{C} is not 1-intersecting. Show that ∣B∣=2n−1|\mathcal{B}|=2^{n-1}.

Let B⊂P([n])\mathcal{B} \subset \mathcal{P}([n]) be 2 -intersecting. Show that ∣B∣⩾2n−2|\mathcal{B}| \geqslant 2^{n-2} is possible. Can the inequality be strict?

Typos? Please submit corrections to this page on GitHub.