组合数学 (Spring 2014)/Problem Set 4

Problem 1

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

Show that for any $k\ge 3$, there exists an $N(k)$ such that every tournament of $n\ge N(k)$ players contains a transitive sub-tournament of $k$ players.

Problem 2

Let $G(U,V,E)$ be a bipartite graph. Let ${\delta }_U$ be the minimum degree of vertices in $U$, and ${\mathrm{\Delta }}_V$ be the maximum degree of vertices in $V$.

Show that if ${\delta }_U\ge {\mathrm{\Delta }}_V$, then there must be a matching in $G$ such that all vertices in $U$ are matched.

Problem 3

Prove the following statement:

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

(Hint: use Dilworth theorem.)

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 $A$ be a Boolean matrix satisfying:

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

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