Math Problems Vault

Problem 5.3.1

(1)(2)

?

(1)

Matching lemma. Suppose there are several (finitely many) boys and girls. Each boy loves some (quite possibly zero) number of girls. Then all the boys can be married to girls they love (so that the married couples do not overlap) if and only if for any set of boys, the number of girls loved by at least one of them is not less than the number of these boys.

(2)

Hall’s theorem. Let $S_{1}, \ldots , S_{m}$ be finite sets. One can choose an element $x_{i} \in S_{i}$ in each of them so that all $x_{i}$ are distinct if and only if for each $k \in \left\{ 1,\ldots ,m\right\}$ the union of any $k$ of these sets has at least $k$ elements.

Problem 5.3.2

What is the minimum number of edges that must be deleted from the graph $K_{n,n}$ so that no perfect matchings remain (i.e., subgraphs consisting of $n$ disjoint segments)?

?

Problem 5.3.3

Suppose that in a system of $m$ -element sets every element belonging to at least one of them belongs to exactly $l$ of them. Then for $m \geqslant l$ this system of sets has an SDR.

?

Remark.

?

Let a family $\mathscr {M}$ of sets be given. In each of the sets an element is chosen. If all these elements are distinct, then such a collection is called a system of distinct representatives (SDR for short). Or, formally, a system of distinct representatives for a family $\mathscr {M}$ of sets is an ordered collection of distinct elements $x(S) \in S$ , $S \in \mathscr {M}$ , i.e., an injective map $x : \mathscr {M} \to \bigcup_{S \in \mathscr {M}} S$ such that $x(S) \in S$ for every $S \in \mathscr {M}$ .

(The ordering of the collection matters for counting the number of SDRs in Problem 5.3.5, not for determining whether an SDR exists.)

For example, Hall's theorem states that a system $S_{1}, \ldots , S_{m}$ of finite sets has a system of distinct representatives if and only if $\left|\bigcup_{i \in I} S_{i}\right| \geqslant \left|I\right|$ for every $I \subset \left\{ 1,\ldots ,m\right\}$ .

Problem 5.3.4

An SDR of a subfamily can be extended to an SDR of the whole family. Here is a more detailed formulation. From a family $\mathscr {M}$ of sets, several subsets $S_{1}, \ldots , S_{k}$ are chosen. Suppose that the elements $x_{1}, \ldots , x_{k}$ form an SDR of the family of sets $S_{1}, \ldots , S_{k} \in \mathscr {M}$ . If the whole family $\mathscr {M}$ has an SDR, then it has an SDR containing the elements $x_{1}, \ldots , x_{k}$ .

?

Problem 5.3.5

(1)(2)(3)

Denote by $F(S_{1}, \ldots , S_{m})$ the number of SDRs of the system $\left\{ S_{1}, \ldots , S_{m}\right\}$ .

?

(1)

Is it true that for every $k$ there exists a system $S_{1}, \ldots , S_{m}$ such that $F(S_{1}, \ldots , S_{m}) = k$ ?

(2)

Find all possible values of $F(S_{1}, S_{2})$ given that $\left|S_{1}\right| = \left|S_{2}\right| = 5$ .

(3)

Find all possible values of $F(S_{1}, S_{2}, S_{3})$ given that $\left|S_{1}\right| = \left|S_{2}\right| = \left|S_{3}\right| = 5$ .

Problem 5.3.6

(1)(2)

Suppose we are given two partitions of a set $S$ into $m$ subsets: $S = \bigsqcup_{i=1}^{m} A_{i} = \bigsqcup_{i=1}^{m} B_{i}$ , $m \leqslant \left|S\right|$ . Suppose one of the following conditions holds.

?

(1)

For every subset $\left\{ i_{1},\ldots ,i_{k}\right\} \subset \left\{ 1,\ldots ,m\right\}$ , the set $A_{i_{1}} \cup \ldots \cup A_{i_{k}}$ contains at most $k$ of the sets $B_{1}, \ldots , B_{m}$ .

(2)

$\left|A_{1}\right| = \ldots = \left|A_{m}\right| = \left|B_{1}\right| = \ldots = \left|B_{m}\right|$ .

Then the sets $A_{1}, \ldots , A_{m}$ can be renumbered so that in the new numbering $A_{i} \cap B_{i} \neq \emptyset$ for every $i = 1, \ldots , m$ .

Problem 5.3.7

Suppose we are given two partitions of a set $S$ into $m$ subsets: $S = \bigsqcup_{i=1}^{m} A_{i} = \bigsqcup_{i=1}^{m} B_{i}$ , $m \leqslant \left|S\right|$ . Suppose that for any subsets $I, J \subset \left\{ 1,\ldots ,m\right\}$ the following inequality holds:

\left|\left(\bigsqcup _{i \in I} A_{i}\right) \cap \left(\bigsqcup _{j \in J} B_{j}\right)\right| \geqslant \left|I\right| + \left|J\right| - m.

Then the sets $A_{1}, \ldots , A_{m}$ can be renumbered so that after the renumbering there exist pairwise distinct elements $x_{i} \in A_{i} \cap B_{i}$ , $i = 1, \ldots , m$ .

?

Remark.

?

Such a collection $x_{1}, \ldots , x_{m}$ is called a common system of distinct representatives of the families of sets $A_{1}, \ldots , A_{m}$ and $B_{1}, \ldots , B_{m}$ .

Problem 5.3.8

(1)(2)

?

(1)

Find a necessary and sufficient condition on a bipartite graph under which its vertices can be labeled $A_{1}, \ldots , A_{n}$ (in the first part) and $B_{1}, C_{1}, \ldots , B_{n}, C_{n}$ (in the second part) so that there are edges $A_{1}B_{1}, A_{1}C_{1}, \ldots , A_{n}B_{n}, A_{n}C_{n}$ .

(2)

Suppose there are $m$ boys and several girls, each boy loves at least $t$ girls, and all the boys can be married to girls they love (so that the married couples do not overlap), i.e., there is a matching. Then there are at least

\begin{cases} t!, & t \leqslant m, \\ t!/(t-m)!, & t > m, \end{cases}

ways to marry off the boys to girls they love.