组合数学 (Fall 2023)/Problem Set 4

Problem 1

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

(Frankl 1986)

Let [math]\displaystyle{ \mathcal{F}\subseteq {[n]\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform family, and suppose that it satisfies that [math]\displaystyle{ A\cap B \not\subset C }[/math] for any [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math].

• Fix any [math]\displaystyle{ B\in\mathcal{F} }[/math]. Show that the family [math]\displaystyle{ \{A\cap B\mid A\in\mathcal{F}, A\neq B\} }[/math] is an anti chain.
• Show that [math]\displaystyle{ |\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor} }[/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{ l/\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].