组合数学 (Spring 2025)/Problem Set 4: Difference between revisions
Created page with "== Problem 1 == Recall that the smallest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''. Prove that: * <math>R(4,3)\leq 9</math>. (Hint: Proof by contradiction. Color the edges of <math>K_9</math> in red and blue, and assume that there are no red triangles and no blue <math>4</math>-cliques. Try to determine the number of red and blue edges adjacent to each vertex.) * <math>R(4,4)\leq 18</math>. ==Problem 2..." |
No edit summary |
||
| Line 1: | Line 1: | ||
== Problem 1 == | == 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 a finite <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. Express <math>N(k)</math> in terms of Ramsey number. | |||
==Problem 2== | == Problem 2== | ||
We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color. | We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show that for any finite <math>r</math> there is a finite <math>N</math> such that for all <math>n\ge N</math>, for any <math>r</math>-coloring of non-empty subsets of <math>[n]</math>, there always exist <math>1\le i<j<k\le n</math> such that the intervals <math>[i,j)=\{i,i+1,\ldots, j-1\}</math>, <math>[j,k)=\{j,j+1,\ldots, k-1\}</math> and <math>[i,k)=\{i,i+1,\ldots, k-1\}</math> are all assigned with the same color. | ||
==Problem 3 == | == Problem 3 == | ||
Let <math>G</math> be a bipartite graph with bipartition <math>A,B</math>. Let <math>a</math> be the minimum degree of a vertex in <math>A</math>,and <math>b</math> the maximum degree of a vertex in <math>B</math>. Prove the following: if <math>a\geq b</math> then there exists a matching of <math>A</math> into <math>B</math>. | |||
== Problem 4 == | == Problem 4 == | ||
Revision as of 05:00, 4 June 2025
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
We color each non-empty subset of [math]\displaystyle{ [n]=\{1,2,\ldots,n\} }[/math] with one of the [math]\displaystyle{ r }[/math] colors in [math]\displaystyle{ [r] }[/math]. Show that for any finite [math]\displaystyle{ r }[/math] there is a finite [math]\displaystyle{ N }[/math] such that for all [math]\displaystyle{ n\ge N }[/math], for any [math]\displaystyle{ r }[/math]-coloring of non-empty subsets of [math]\displaystyle{ [n] }[/math], there always exist [math]\displaystyle{ 1\le i\lt j\lt k\le n }[/math] such that the intervals [math]\displaystyle{ [i,j)=\{i,i+1,\ldots, j-1\} }[/math], [math]\displaystyle{ [j,k)=\{j,j+1,\ldots, k-1\} }[/math] and [math]\displaystyle{ [i,k)=\{i,i+1,\ldots, k-1\} }[/math] are all assigned with the same color.
Problem 3
Let [math]\displaystyle{ G }[/math] be a bipartite graph with bipartition [math]\displaystyle{ A,B }[/math]. Let [math]\displaystyle{ a }[/math] be the minimum degree of a vertex in [math]\displaystyle{ A }[/math],and [math]\displaystyle{ b }[/math] the maximum degree of a vertex in [math]\displaystyle{ B }[/math]. Prove the following: if [math]\displaystyle{ a\geq b }[/math] then there exists a matching of [math]\displaystyle{ A }[/math] into [math]\displaystyle{ B }[/math].
Problem 4
Suppose that [math]\displaystyle{ M,M' }[/math] are matchings in a bipartite graph [math]\displaystyle{ G }[/math] with bipartition [math]\displaystyle{ A,B }[/math]. Suppose that all the vertices of [math]\displaystyle{ S\subseteq A }[/math] are matched by [math]\displaystyle{ M }[/math] and that all the vertices of [math]\displaystyle{ T\subseteq B }[/math] are matched by [math]\displaystyle{ M' }[/math]. Prove that [math]\displaystyle{ G }[/math] contains a matching that matches all the vertices of [math]\displaystyle{ S \cup T }[/math].
Problem 5
Use the König-Egerváry theorem to prove the followings:
- Every bipartite graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ l }[/math] edges has a matching of size at least [math]\displaystyle{ l/\Delta(G) }[/math], where [math]\displaystyle{ \Delta(G) }[/math] is the maximum degree of a vertex in [math]\displaystyle{ G }[/math].
- Let [math]\displaystyle{ A }[/math] be a 0-1 matrix with [math]\displaystyle{ m }[/math] 1s. Let [math]\displaystyle{ s }[/math] be the maximal number of 1s in a row or column of [math]\displaystyle{ A }[/math], and suppose that [math]\displaystyle{ A }[/math] has no square [math]\displaystyle{ r\times r }[/math] all-1 sub-matrix. It requires at least [math]\displaystyle{ m/(sr) }[/math] all-1 (not necessarily square) sub-matrices to cover all 1s in [math]\displaystyle{ A }[/math].