组合数学 (Fall 2016)/Problem Set 5
An -player tournament (竞赛图) is said to be transitive, if there exists a permutation of such that for every .
Show that for any , there exists a finite such that every tournament of players contains a transitive sub-tournament of players. Express in terms of Ramsey number.
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.
Use Dilworth theorem to prove the following statement:
- For any distinct finite sets , there always is a collection such that and for any different we have .
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 .