Math Problems Vault

Problem 5.1.1

Prove that any family of pairwise intersecting subsets of an $n$ -element set contains at most $2^{n-1}$ subsets.

?

Problem 5.1.2

(1)(2)

Let $2 \leqslant t \leqslant n-2$ .

?

(1)

Construct a family of $2^{n-t}$ subsets of an $n$ -element set any two of which intersect in at least $t$ elements.

(2)

Does there exist such a family of $2^{n-t}+1$ subsets?

Problem 5.1.3

(1)(2)

Let $\mathscr {F}$ be any family of $k$ -element subsets of an $n$ -element set.

?

(1)

If $2k \leqslant n$ and any two subsets from $\mathscr {F}$ intersect, then $\left|\mathscr {F}\right| \leqslant \binom {n-1}{k-1}$ .

(2)

If $2k \geqslant n$ and the union of no two subsets from $\mathscr {F}$ is the whole $n$ -element set, then $\left|\mathscr {F}\right| \leqslant \binom {n-1}{k}$ .

Problem 5.1.4

Any family of twenty 5-element subsets of a 15-element set can be partitioned into 6 subfamilies so that any two disjoint subsets lie in different subfamilies.

?

Remark.

?

In such situations (see Sec. 7.1) one usually speaks of a coloring in different colors instead of a partition into subfamilies. Then, contrary to the intuitive idea of coloring, it is the sets that are colored, while their elements are not colored.

Problem 5.1.5

(1)(2)(3)(4)

For $l < k$ , denote by $M(n,k,l)$ the minimum number of $k$ -element subsets of the set $\mathscr {R}_{n}$ such that every $l$ -element subset of the set $\mathscr {R}_{n}$ is entirely contained in at least one of them. For example, Problem 1.6.2 (1) states that $M(n,k,l) \geqslant \binom {n}{l} / \binom {k}{l}$ .

?

(1)

Find $M(n,k,1)$ .

(2)

Find $M(6k+3,3,2)$ .

(3)

Find $M(n,3,2)$ .

(4)

Prove that $M(n,k,l) \geqslant nM(n-1,k-1,l-1)/k$ .