组合数学 (Fall 2016)/Problem Set 5: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "==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..."
 
imported>Etone
 
(One intermediate revision by the same user not shown)
Line 10: Line 10:


== Problem 3 ==
== Problem 3 ==
Prove the following statement:
Use Dilworth theorem to 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>.
* 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>.
== 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  and every column 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>.

Latest revision as of 10:41, 4 December 2016

Problem 1

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

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

Problem 2

Let [math]\displaystyle{ G(U,V,E) }[/math] be a bipartite graph. Let [math]\displaystyle{ \delta_U }[/math] be the minimum degree of vertices in [math]\displaystyle{ U }[/math], and [math]\displaystyle{ \Delta_V }[/math] be the maximum degree of vertices in [math]\displaystyle{ V }[/math].

Show that if [math]\displaystyle{ \delta_U\ge \Delta_V }[/math], then there must be a matching in [math]\displaystyle{ G }[/math] such that all vertices in [math]\displaystyle{ U }[/math] are matched.

Problem 3

Use Dilworth theorem to prove the following statement:

  • For any [math]\displaystyle{ n }[/math] distinct finite sets [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math], there always is a collection [math]\displaystyle{ \mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\} }[/math] such that [math]\displaystyle{ |\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor }[/math] and for any different [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math] we have [math]\displaystyle{ A\cup B\neq C }[/math].

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]\displaystyle{ A }[/math] be a Boolean matrix satisfying:

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

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