Lesson 3

Optional Problems.

1. (20 points) Prove that if for all \(k \in \mathbb{Z}_{> 0}\), \(W(k, 2)\) exists, then for all \(k, r \in \mathbb{Z}_{> 0}\), \(W(k, r)\) exists (without referencing to the proof of Van der Waerden theorem).
2. (20 points) Let \(M \in \mathbb{Z}_{>0}\) be such that for every \((M - 1)\)-coloring of \(\mathbb{Z}_{>0}\), at least one color class contains arbitrarily long arithmetic progressions. Let \(S = \{ s_{i} \}_{i \ge 0}\) be a strictly increasing sequence such that for all \(i \ge 0\), the difference satisfies \(|s_{i + 1}- s_{i}| \le M\). Prove that the sequence \(S\) contains arbitrarily long arithmetic progressions.
3. (20 points) Design a randomized algorithm that, given three matrices \(A, B, C \in \mathbb{F}_{p}^{n \times n}\) (where \(p\) is not too large: \(p = n^{O(1)}\)), verifies whether \(A \cdot B = C\) holds, with high probability, in time \(O(n^{2}\log n)\).
4. (25 points) Consider all nonzero multilinear (i.e., of degree at most 1 in each variable) polynomials in \(n\) variables \(x_{1}, x_{2}, \dotsc, x_{n}\) over the field \(\mathbb{Z}_{p}\) where \(p\) is prime. Prove that among them, the polynomial \(x_{1} x_{2} \dotsb x_{n}\) has the maximum number of zeros on the entire set of possible inputs \(\mathbb{Z}_{p}^{n}\).
5. (65 points) Given a bipartite graph \(G = (U \sqcup V, E)\) with \(n\) vertices in each part (vertices are numbered from \(1\) to \(n\)), consider the following \(n \times n\) matrix \(A\): \[A_{i,j}= \begin{cases}x_{ij}, & \text{if there is an edge } (i, j) \in E,\\ 0, & \text{otherwise}.\end{cases}\]
   1. (10 points) Prove that \(\det(A) \neq 0\) if and only if there exists a perfect matching in \(G\).
   2. (10 points) Describe an algorithm that computes the size of the maximum matching in \(G\) in time \(O(n^{\omega})\) using the probabilistic method (here, \(\omega\) is the matrix-multiplication exponent).
   3. (20 points) Describe an algorithm that finds a maximum matching (as a set of edges) in bipartite graph \(G\). At first do it in time \(O(n^{\omega + 2})\), then improve it to \(O(n^{\omega + 1})\).
   4. (25 points) Design an algorithm that finds a maximum matching in a regular graph (not necessarily bipartite) in time \(O(n^{\omega + 1})\).
   Hint:

   For the third item, you might want to read about adjugate matrices and reduce your problem to find some perfect matching.