## Matchings - In a graph $G$, a **matching** $M$ is a subgraph whose edges are all disjoint. - A matching is **perfect** if every vertex is in the matching. - A graph $G$ is a **bipartite** if it has **parts** $A,B$ where all edges cross the two parts. - A path $P \subseteq G$ is **$M$-alternating** if every other edge of it is in $M$. - The **inversion** $P-M$ is also a matching on $G$. - An $M$-alternating path $P$ is **$M$-augmenting** if its ends are not in $M$. ### Maximal Size Matchings - A matching $M \subseteq G$ is not maximal $\iff \exists$ some $M$-augmenting path $P$. - Hence by finding $M$-augmenting paths and inverting it to be the new $M$, we can successively increase the size of the matching (until there are no more augmenting paths). - Let $G$ be a bipartite, and given a matching $M$, define the "uncovered" parts $A^{*}=A-M$, and $B^*=B-M$. Let all edges in $M$ run $B \to A$ and all in $G-M$ run $A \to B$. Then an $M$-augmenting path is a path $A^{*}\to B^{*}$ on the directed graph $G$. - Hence the maximal-sized matching problem is reduced to finding paths on a directed bipartite. - To find such a path, the **search algorithm** finds all vertices reachable from $A^{*}$: - Start with the "reachable" set $R = A^{*}$. - If there is any directed edge going out of $R$, add the end of the edge to $R$. - If there are no more such edges, end the algorithm; if $R$ intersects $B^*$, then a direct path $A^{*}\to B^*$ exists. - The **Hungarian algorithm** then uses this search to successively increase the size of the matching $M$, until it is maximal: - Start with $M = \emptyset$. - Let $A^*,B^*$ be the parts not covered by the current $M$. Use the search algorithm to find a directed path between them. - The path is $M$-augmenting, so invert it to get a larger matching $M$. Repeat until no more paths exist between $A^{*}, B^*$. ### Matchings and Covers - A **cover** of graph $G$ is a set of vertices $C \subseteq V(G)$ such that every edge intersects $C$. - If $M$ is a matching and $C$ a cover in $G$, then $|M|\le |C|$. - **König's theorem**: in a bipartite $G$, the maximal matching and the minimal cover have the same size. ### Perfect Matchings - A matching $M$ is **perfect** if it covers every vertex of $G$. - A **neighborhood** of a set $S \subseteq G$ is the set $N(S)=\{ t \in V(G)\,|\, \exists s \in S, \,s,t \text{ are neighbors} \}$ If $G$ is a bipartite, **Hall's (marriage) theorem** guarantees the existence of a matching covering $A$, if every subset of $A$ is no larger than its neighbor: $\forall S \subseteq A,\,|S| \le |N(S)|$where $A,B$ are the two parts of the bipartite $G$. - Hence if this condition is satisfied by both $A,B$, then there is a perfect matching, and in particular $|A|=|B|$. > [!proof] Proof with Menger's Theorem (for edge connectedness) > Let $G=(V_{1} \cup V_{2}, E)$ by a bipartite graph, and assume that Hall's condition holds. > > Now let $G^{\ast}$ be a copy of $G$, but with two extra vertices $s,t$ where $s$ is connected to $\forall v \in V_{1}$, and $t$ to $\forall v \in V_{2}$: ![[HallAddedVertex.png|center|w60]] > Now obviously $\lambda(s,t) \le | V_{1} |$ (removing all edges from $s$), and by Menger's theorem (edge version), $\lambda(s,t)$ is the largest number of edge-disjoint $st$-paths in $G^{\ast}$, which are just matchings in $G$. Therefore, we wish to show that $\lambda(s,t)=| V_{1} |$. > > To do so, consider any subset of edges $A \subset E(G^{\ast})$ to remove, and we shall show that if $| A | < | V_{1} |,$ it fails to disconnect $s,t$. Now separate $A$ between $s, V_{1}, V_{2}, t$: ![[HallPartsOfRemoval.png|center|w60]] > We attempt to find a path from $s$ to $t$. Firstly, start from $s$ and go to $V_{1}$. Since $| A_{s} | \le | A | < | V_{1} |,$ so there are vertices that "survived" $A_{s}$, i.e. the set $\begin{align*} V_{1}^{\ast}&:= \{ v \in V_{1} ~|~ sv_{1} \not \in A_{s} \} \subseteq V_{1}, \\[0.4em] | V_{1}^{\ast} |&= | V_{1} |-| A_{s} |. \end{align*}$Now we attempt to go from $V_{1}^{\ast}$ to $N(V_{1}^{\ast})$, where $A_{v}$ cut off at most $| A_{v} |$ of them. However, by assumption of Hall's condition, $| N(V_{1}^{\ast}) | \ge | V_{1}^{\ast} | =| V_{1} |- | A_{s} | > | A |-| A_{s} | \ge | A_{v} |,$so not all of them are cutoff: we can reach a non-empty subset $\begin{align*} V_{2}^{\ast} &:= \{ v \in V_{2} ~|~ \exists v_{1} \in V_{1}^{\ast}:~v_{1}v \not \in A_{v} \}.\\[0.4em] | V_{2}^{\ast} | &\ge | N(V_{1}^{\ast}) |-| A_{s} | \ge | V_{1}^{\ast} |-| A_{v} |. \end{align*}$From there we can finally go to $t$: again $A_{t}$ cuts off at most $| A_{t} |$ edges, but a similar calculation shows that $| V_{2}^{\ast} |\ge | V_{1}^{\ast} |-| A_{v} | = | V_{1} |-| A_{s} |-| A_{v} |> | A |-| A_{s} |-| A_{v} |=| A_{t} |.$Therefore not all edges are gone. This shows that any $A: | A | \lneq | V_{1} |$ fails to disconnect $s,t$, forcing $\lambda(s,t) \ge | V_{1} |$, and the equality follows.