组合数学 (Spring 2025)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Gispzjz (talk | contribs)
140 edits
No edit summary
Gispzjz (talk | contribs)
140 edits
 
Line 4: Line 4:
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.
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.
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 3 ==
== Problem 3 ==

Latest revision as of 05:04, 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

Recall that the smallest number [math]\displaystyle{ R(k,\ell) }[/math] satisfying the condition in the Ramsey theory is called the Ramsey number. Prove that:

  • [math]\displaystyle{ R(4,3)\leq 9 }[/math]. (Hint: Proof by contradiction. Color the edges of [math]\displaystyle{ K_9 }[/math] in red and blue, and assume that there are no red triangles and no blue [math]\displaystyle{ 4 }[/math]-cliques. Try to determine the number of red and blue edges adjacent to each vertex.)
  • [math]\displaystyle{ R(4,4)\leq 18 }[/math].

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].
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Spring_2025)/Problem_Set_4&oldid=13193"