组合数学 (Fall 2016)/Problem Set 5

Problem 1

An $\displaystyle{ n }$-player tournament (竞赛图) $\displaystyle{ T([n],E) }$ is said to be transitive, if there exists a permutation $\displaystyle{ \pi }$ of $\displaystyle{ [n] }$ such that $\displaystyle{ \pi_i\lt \pi_j }$ for every $\displaystyle{ (i,j)\in E }$.

Show that for any $\displaystyle{ k\ge 3 }$, there exists a finite $\displaystyle{ N(k) }$ such that every tournament of $\displaystyle{ n\ge N(k) }$ players contains a transitive sub-tournament of $\displaystyle{ k }$ players. Express $\displaystyle{ N(k) }$ in terms of Ramsey number.

Problem 2

Let $\displaystyle{ G(U,V,E) }$ be a bipartite graph. Let $\displaystyle{ \delta_U }$ be the minimum degree of vertices in $\displaystyle{ U }$, and $\displaystyle{ \Delta_V }$ be the maximum degree of vertices in $\displaystyle{ V }$.

Show that if $\displaystyle{ \delta_U\ge \Delta_V }$, then there must be a matching in $\displaystyle{ G }$ such that all vertices in $\displaystyle{ U }$ are matched.

Problem 3

Use Dilworth theorem to prove the following statement:

• For any $\displaystyle{ n }$ distinct finite sets $\displaystyle{ S_1,S_2,\ldots,S_n }$, there always is a collection $\displaystyle{ \mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\} }$ such that $\displaystyle{ |\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor }$ and for any different $\displaystyle{ A,B,C\in\mathcal{F} }$ we have $\displaystyle{ A\cup B\neq C }$.

Problem 4

A Boolean matrix is a matrix whose entries are either 0 or 1. We call a matrix 1-matrix if all its entries are 1.

Let $\displaystyle{ A }$ be a Boolean matrix satisfying:

• there are totally $\displaystyle{ m }$ 1-entries in $\displaystyle{ A }$;
• every row and every column of $\displaystyle{ A }$ contains at most $\displaystyle{ s }$ 1-entries;
• $\displaystyle{ A }$ does not contain any $\displaystyle{ r\times r }$ 1-matrix as submatrix.

Use König-Egerváry Theorem to prove: we need at least $\displaystyle{ \frac{m}{sr} }$ many 1-matrices to precisely cover all the 1-entries in $\displaystyle{ A }$.