Matchings · Theory Problems

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Basic Problems.

  1. (5 points) More than a hundred people from different countries are present at the forum. It is known that among any three people there are two who can speak to each other in some common language. Prove that there exist three people who can all talk to one another.
  2. (10 points) There are \(n\) teams and \(m\) interns. Team \(i\) wants to hire \(k_{i}\in\mathbb{N}\) interns, all chosen from \(A_{i}\subseteq [m]\). Show that all teams can get the required number of interns from their desired sets if and only if for any set of teams \(S\subseteq [n]\), \[\left|\bigcup_{i\in S}A_{i}\right| \ge \sum_{i\in S}k_{i}.\]
    Hint:
    Reduce to Hall’s theorem by replacing team \(i\) with \(k_{i}\) identical copies (each needing one intern).
  3. (10 points) Let \(G=K_{17}\) be the complete graph on \(17\) vertices. The edges are colored in three colors: red, blue, and green. Prove that there must be a monochromatic triangle.
  4. (10 points) Show that if \(G=(A\sqcup B,E)\) is a bipartite graph such that \(|N(S)|\ge |S|-d\) holds for every \(S\subseteq A\), then \(G\) has a matching with at least \(|A|-d\) edges.
  5. (10 points) Prove that for any graph \(G=(V,E)\), the following inequality holds: \[\alpha(G) \ge \frac{|V|}{\Delta(G)+1},\] where \(\Delta(G)\) is the maximum degree of \(G\).
    Hint:
    Try a greedy procedure.
  6. (10 points)
    • Suppose in a bipartite graph \(G = (V_{1}, V_{2}, E)\) every vertex in \(V_{1}\) has degree at least \(k\), and every vertex in \(V_{2}\) has degree at most \(k\). Show that there exists a matching that covers \(V_{1}\).

    • Let \(G = (V_{1}, V_{2}, E)\) be a \(k\)-regular bipartite graph. Prove that \(G\) is the union of \(k\) perfect matchings.

  7. (10 points) Let \(G\) be a bipartite graph with each part of size \(2n\) and minimum degree at least \(n\). Prove that \(G\) has a perfect matching.
  8. (15 points) The Gale–Shapley algorithm produces stable matchings on complete bipartite graphs. Consider instead a complete graph on an even number of vertices, where each vertex has a strict preference list over all other vertices, and a matching is stable if it has no blocking pair. Is there always a stable matching in such a graph?
  9. (15 points) Let \(M\) be a matching in a graph \(G\). A path is called \(M\)-alternating if its edges alternately belong to \(M\) and do not belong to \(M\). Also, an \(M\)-alternating path is called \(M\)-augmenting if its endpoints are not covered by the matching \(M\). Prove that a matching \(M\) in a graph \(G\) is maximum if and only if there are no \(M\)-augmenting paths.
  10. (15 points) In the lecture, an algorithm for stable matching was described (Gale–Shapley with proposals from the left part). Show that it finds for each left-part vertex its best possible partner among all stable matchings, and for each right-part vertex its worst possible partner among all stable matchings. More formally, for a left-part vertex \(v\) let \(\operatorname{best}(v)\) be the best (for \(v\)) right-part vertex \(u\) such that there exists a stable matching pairing \(v\) with \(u\). Similarly, for a right-part vertex \(u\) let \(\operatorname{worst}(u)\) be its worst possible partner \(v\) among all stable matchings. Prove that \[\{(v,\text{best}(v))\}_{v}=\{(\text{worst}(u),u)\}_{u}\] and that this is exactly the matching produced by the algorithm.
  11. (15 points) In a rectangular matrix of nonnegative reals with \(m\) rows and \(n\) columns, each row and each column contains at least one positive element. Moreover, if a row and a column intersect in a positive element, then the sums of their elements are the same. Prove that \(m=n\).
    Hint:
    Build a bipartite graph “rows vs columns” using positive entries.
  12. (15 points) Consider an undirected graph \(G\). Two players are playing the following game on this graph. The first player places a stone on some vertex. Then, the second player moves the stone to an adjacent vertex. The players alternate turns moving the stone to an adjacent vertex. During the game, the stone must never visit the same vertex twice. The player who cannot make a move loses. Determine the optimal strategy for the graph \(G\) and determine who will win.