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

==Problem 1 ==
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.

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

== Problem 2 ==
Let <math>G(U,V,E)</math> be a bipartite graph. Let <math>\delta_U</math> be the '''minimum''' degree of vertices in <math>U</math>, and <math>\Delta_V</math> be the maximum degree of vertices in <math>V</math>.

Show that if <math>\delta_U\ge \Delta_V</math>, then there must be a matching in <math>G</math> such that all vertices in <math>U</math> are matched.

== Problem 3 ==
Prove the following statement:
* For any <math>n</math> distinct finite sets <math>S_1,S_2,\ldots,S_n</math>, there always is a collection <math>\mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\}</math> such that <math>|\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor</math> and for any different <math>A,B,C\in\mathcal{F}</math> we have <math>A\cup B\neq C</math>.

(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 <math>A</math> be a Boolean matrix satisfying:
* there are totally <math>m</math> 1-entries in <math>A</math>;
* every row  <font color=red>and every column</font> of <math>A</math> contains at most <math>s</math> 1-entries;
* <math>A</math> does not contain any <math>r\times r</math> 1-matrix as submatrix.
Use König-Egerváry Theorem to prove: we need at least <math>\frac{m}{sr}</math> many 1-matrices to precisely cover all the 1-entries in <math>A</math>.