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

From EtoneWiki
Jump to: navigation, search

Problem 1

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.

Problem 2

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.

Problem 3

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.)

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 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 .