# 组合数学 (Fall 2016)/Problem Set 5

Jump to: navigation, search

## Problem 1

An ${\displaystyle n}$-player tournament (竞赛图) ${\displaystyle T([n],E)}$ is said to be transitive, if there exists a permutation ${\displaystyle \pi }$ of ${\displaystyle [n]}$ such that ${\displaystyle \pi _{i}<\pi _{j}}$ for every ${\displaystyle (i,j)\in E}$.

Show that for any ${\displaystyle k\geq 3}$, there exists a finite ${\displaystyle N(k)}$ such that every tournament of ${\displaystyle n\geq N(k)}$ players contains a transitive sub-tournament of ${\displaystyle k}$ players. Express ${\displaystyle N(k)}$ in terms of Ramsey number.

## Problem 2

Let ${\displaystyle G(U,V,E)}$ be a bipartite graph. Let ${\displaystyle \delta _{U}}$ be the minimum degree of vertices in ${\displaystyle U}$, and ${\displaystyle \Delta _{V}}$ be the maximum degree of vertices in ${\displaystyle V}$.

Show that if ${\displaystyle \delta _{U}\geq \Delta _{V}}$, then there must be a matching in ${\displaystyle G}$ such that all vertices in ${\displaystyle U}$ are matched.

## Problem 3

Use Dilworth theorem to prove the following statement:

• For any ${\displaystyle n}$ distinct finite sets ${\displaystyle S_{1},S_{2},\ldots ,S_{n}}$, there always is a collection ${\displaystyle {\mathcal {F}}\subseteq \{S_{1},S_{2},\ldots ,S_{n}\}}$ such that ${\displaystyle |{\mathcal {F}}|\geq \lfloor {\sqrt {n}}\rfloor }$ and for any different ${\displaystyle A,B,C\in {\mathcal {F}}}$ we have ${\displaystyle A\cup B\neq C}$.

## 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 ${\displaystyle A}$ be a Boolean matrix satisfying:

• there are totally ${\displaystyle m}$ 1-entries in ${\displaystyle A}$;
• every row and every column of ${\displaystyle A}$ contains at most ${\displaystyle s}$ 1-entries;
• ${\displaystyle A}$ does not contain any ${\displaystyle r\times r}$ 1-matrix as submatrix.

Use König-Egerváry Theorem to prove: we need at least ${\displaystyle {\frac {m}{sr}}}$ many 1-matrices to precisely cover all the 1-entries in ${\displaystyle A}$.