组合数学 (Spring 2024)/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{ \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].

Problem 6 (Bonus Problem)

This is a bonus problem worth [math]\displaystyle{ 10 }[/math] points, the score of which will be used to replace the lowest score of any other problem in all problem sets. (Nothing will be done if this problem is already the lowest-scored problem)

A company with [math]\displaystyle{ n }[/math] two-person teams researching products adapted to the pandemic by scheduling so no more than [math]\displaystyle{ n }[/math] individuals were in the office simultaneously, ensuring smooth operations even post-pandemic. They organized teams numbered [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ n }[/math], with members labeled [math]\displaystyle{ (i, 1) }[/math] and [math]\displaystyle{ (i, 2) }[/math]. Each week, one team member works onsite, while the other works remotely, maintaining productivity without in-person meetings between team members. The employees [math]\displaystyle{ (i, 1) }[/math] and [math]\displaystyle{ (i, 2) }[/math] know each other well and collaborate productively regardless of being isolated from each other, so members of the same team do not need to meet in person in the office. However, isolation between members from different teams is still a concern.

Each pair of teams [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] for [math]\displaystyle{ i\neq j }[/math] has to collaborate occasionally. For a given number [math]\displaystyle{ w }[/math] of weeks and for fixed team members [math]\displaystyle{ (i,a) }[/math] and [math]\displaystyle{ (j,b) }[/math], let [math]\displaystyle{ w_1\lt w_2\lt \dots\lt w_k }[/math] be the weeks in which these two team members meet in the office. The isolation of those two people is the maximum of

[math]\displaystyle{ \{w_1,w_2-w_1,w_3-w_2,\dots,w_k-w_{k-1},w+1-w_k\}, }[/math]

or infinity if those two people never meet. The isolation of the whole company is the maximum isolation across all choices of [math]\displaystyle{ i, j, a }[/math] and [math]\displaystyle{ b }[/math].

Given [math]\displaystyle{ n }[/math] and [math]\displaystyle{ w }[/math], let [math]\displaystyle{ f(n,w) }[/math] be the minimum isolation over all possible schedules. For example, [math]\displaystyle{ f(2,3)=\infty }[/math] and [math]\displaystyle{ f(2,6)=4. }[/math] Give an expression for [math]\displaystyle{ f(n,w) }[/math] and explain your answer. (Hint: View a schedule for one team as a binary string [math]\displaystyle{ \mathbf{x} }[/math] of length [math]\displaystyle{ w }[/math], with [math]\displaystyle{ \mathbf{x}_i = 0 }[/math] indicating that the first team member comes to work on day [math]\displaystyle{ i }[/math], and [math]\displaystyle{ x_i= 1 }[/math] indicating that the second team member comes to work on day [math]\displaystyle{ i }[/math]. What is the criterion between any two binary strings if we need the isolation being at most [math]\displaystyle{ k }[/math] for some integer [math]\displaystyle{ k }[/math]?)