B1.5

Combinatorics | Part II, 2001

Let A[n](r)\mathcal{A} \subset[n]^{(r)} where rn/2r \leqslant n / 2. Prove that, if A\mathcal{A} is 1-intersecting, then A(n1r1)|\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 BP([n])\mathcal{B} \subset \mathcal{P}([n]) be maximal 1-intersecting; that is, B\mathcal{B} is 1-intersecting but if BCP([n])\mathcal{B} \subset \mathcal{C} \subset \mathcal{P}([n]) and BC\mathcal{B} \neq \mathcal{C} then C\mathcal{C} is not 1-intersecting. Show that B=2n1|\mathcal{B}|=2^{n-1}.

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

Typos? Please submit corrections to this page on GitHub.