组合数学 (Spring 2014)/Problem Set 4
An -player tournament (竞赛图) is said to be transitive, if there exists a permutation of such that for every .
Show that for any , there exists an such that every tournament of players contains a transitive sub-tournament of players.
Let be a bipartite graph. Let be the minimum degree of vertices in , and be the maximum degree of vertices in .
Show that if , then there must be a matching in such that all vertices in are matched.
Prove the following statement:
- For any distinct finite sets , there always is a collection such that and for any different we have .
(Hint: use Dilworth theorem.)
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 be a Boolean matrix satisfying:
- there are totally 1-entries in ;
- every row and every column of contains at most 1-entries;
- does not contain any 1-matrix as submatrix.
Use König-Egerváry Theorem to prove: we need at least many 1-matrices to precisely cover all the 1-entries in .