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

## Contents

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