组合数学 (Spring 2025)/Problem Set 4

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