5.26 Matching in bipartite graphs

We want to match workers and jobs respecting the given condition

Definition

A graph \(G\) is called bipartite if there is a decomposition \(V=V_{0}\sqcup V_{1}\) of the set of vertices such that

\(V_{0},V_{1}\neq \empty\)
If \(e\in E,e=\{uv\}\), then either \(u\in V_{0},v\in V_{1}\) or \(u\in V_1,v\in V_0\)

We usually assume that \(\#V_0\leq \#V_1\)

A matching in a bipartite graph \(G\) is its subgraph \(G'\) s.t. the degrees of all the vertices of \(G'\) are equal to \(1\)

We say that a matching is saturating if \(\forall v\in V_0\) its degree \(G'\) is exactly \(1\)

Perfect matching is a saturating matching is the case when \(\#V_0=\#V_1\)

Let \(G\) be graph \(u\in V\) be vertex of \(G\), \(N(u)=\{v\in V:\text{ u and v are adjacent}\}\) where \(N\) refers to neighbourhood

Given a subset \(S\subset V\), then \(N(S)=\bigcup_{u\in S}N(u)\)

Theorem(Hall's marriage theorem)

Let \(G\) be a bipartite graph and \(V=V_0\sqcup V_1\), then \(G\) admits a saturating matching if and only if \(\forall S\subseteq V_{0}\) we have \(\#S\leq \#N(S)\) (the hall's condition)

Proof(Important)

\(\Rightarrow\)) Trivial

\(\Leftarrow\)) Induction by \(\#V_0\)

Base case: \(\#V_0=1\), then there exists a matching

Induction step: Suppose Hall's condition\(\implies\)existence of a saturating matching for any bipartite graph \(\#V_0\leq k\)

Take a bipartite graph \(G\) with \(\#V_0=k+1\) and \(G\) satisfies the Hall's condition

Case 1: \(\forall S\subsetneq V_0,S\neq \empty\), we have \(\#N(S)\geq \#S+1\)

Consider an edge \(\{uv\}\) \(u\in V_0,v\in V_1\), try to include this edge to a matching

Consider \(G-\{u\}-\{v\}=G'\), claim: \(G'\) still satisfies the Hall's condition

Let \(V_0'=V_0-\{u\}\) and \(V_1'=V_1-\{v\}\), take \(S\subseteq V_0'\)

\(\#N_{G'}(S)\geq\#N_G(S)-1\geq( \#S+1)-1=\#S\), the

Thus Hall's condition holds for \(G'\)

Case 2: \(\exists S\subsetneq V_{0},S\neq \empty\) s.t. \(\#N_G(S)=\#S\)

Consider \(G[S\cup N_{G}(S)]\) graph. It satisfy the Hall's condition.

Then the saturating matching exists in \(G[S\cup N_{G}(S)]\)

Consider \(V_0'=V_0-S\), \(V_1'=V_1-N_G(S)\), let \(G'=G[V_0'\cup V_1']\). Claim: \(G'\) satisfy the Hall's condition

Suppose the Hall's condition doesn't hold true for \(G'\), then \(\exists T\subseteq V_0'\) s.t. \(\#N_{G'}(T)<\#T\)

Compute \(\#N_{G}(S\cup T)=\#(N_{G}(S)\cup N_{G'}(T))\overset{\text{since they are disjoint}} {=}\#N_{G}(S)+\#N_{G'}(T)<\#S+\#T\)

Note \(S\cup T\) are also disjoint, then \(\#(S\cup T)=\#S+\#T\), thus \(\#N_{G}(S\cup T)<\#(S\cup T)\)

Then contradiction to the Hall's condition

Gale-Shapley algorithm for construction of a stable matching

Simplest version

Let \(b_1,...,b_n\) be boys and \(g_1,...,g_n\) be girls, for every boy, there is a complete order on the set of girls. \(\forall i= 1,...,n\) order \(\leq_{b_i}\) on \(G\)

For every girl, there is a complete order on the set of boys. \(\forall i= 1,...,n\) order \(\leq _{g_i}\) on \(B\)

Bad(unstable) matching

A matching is stable if it doesn't have unstable pairs. This algorithm allows to construct a stable matching

Algorithm: Initially, no one is engaged. Several rounds: During each round, every boy that is not engaged proposes to the highest ranked girl of his list that did not reject him yet.

If a girl receives several proposals, she rejects all except for the best one, and replies "maybe" to the best one she has

The boy, that receives maybe is considered to be engaged to that girl. The rejected boys are not engaged

The algorithm stops, when every boy is engaged

Example

Everyone is matched: If there is an unmatched boy(all his proposals have been rejected) and an unmatched girl, at some point he should have proposed to this girl, then she had a better candidate.

So this situation is not possible

For example of bob and alice

If bob is engaged to jane, then at some point before, he proposed to alice (since pop likes alice more) and alice refused.

Then alice had a better option, then she like her current partner more than bob. But alice likes bob more than richasd, thus this is impossible

For the same list of preferences, we can have several stable matching

\(M_{1}\geq_{B} M_2\) if \(\forall b\in B,m_1(b)\geq_b m_2(b)\) \(M_{1}\geq_{G}M_{2}\) if \(\forall g\in G,m_{1}(g)\geq_{g}m_{2}(g)\)

Output of the GS algorithm is the best one for the boys and the worst one for the girls

Dorm room arrangement problem

‍