Chapter 12: Systems of Distinct Representatives and Matchings

When can every applicant receive a distinct acceptable choice?

Four applicants want four distinct slots. Each applicant lists the slots they can accept. Having four applicants and four slots is necessary, but it does not ensure an assignment: several applicants may depend on the same small group of slots.

Represent the data by a finite bipartite graph $G=(L,R,E)$. The disjoint sets $L$ and $R$ contain applicants and slots; an edge $(a,r)$ means applicant $a$ accepts slot $r$. A matching is a set of edges with no shared endpoint. It saturates $L$ when every applicant belongs to one matched edge. It is perfect when it covers every vertex on both sides. Saturating $L$ permits unused slots if $|R|>|L|$.

We will learn to return either an assignment or a checkable obstruction. Preferences introduce a separate question—stability—and later optional sections connect matching counts and existence to polynomials and linear inequalities.

12.1 Hall's marriage theorem

For $S\subseteq L$, define its neighborhood

$$ N(S)=\{r\in R:\text{ some }a\in S\text{ has }(a,r)\in E\}. $$

Hall's theorem states that a finite bipartite graph has a matching saturating $L$ if and only if

$$ |N(S)|\ge |S|\qquad\text{for every }S\subseteq L. $$

Necessity is the pigeonhole principle applied to each group: a matching gives the members of $S$ distinct partners, all belonging to $N(S)$. Checking just $S=L$ misses smaller bottlenecks.

For sufficiency, choose a matching $M$ of maximum size; one exists because the graph is finite. Suppose it leaves an applicant $a_0$ unmatched. Direct each edge outside $M$ from $L$ to $R$, and each matched edge from $R$ to $L$. Let $Z_L,Z_R$ be the vertices reachable from $a_0$ on their respective sides.

A directed path to an unmatched slot would alternate between unmatched and matched edges, starting and ending with unmatched edges. Replacing its matched edges by its unmatched edges increases the matching size by one: internal vertices keep one partner, and the two endpoints acquire partners. Such a path is called augmenting, and maximum size excludes it.

Consequently every vertex of $Z_R$ is matched. Its partner lies in $Z_L$, and every vertex of $Z_L$ except $a_0$ was reached along its matched edge. Matching edges therefore give a bijection between $Z_R$ and $Z_L\setminus\{a_0\}$, so

$$|Z_R|=|Z_L|-1.$$

Moreover, $N(Z_L)=Z_R$. Every unmatched edge out of $Z_L$ can be followed; the matched partner of a reached applicant was already reached, except that $a_0$ has no partner. Conversely, each reached slot is adjacent to a reached applicant. Thus $Z_L$ violates Hall's condition, a contradiction. This proves sufficiency and explains how a failed augmentation supplies a certificate.

In the motivating feasible instance, a matching exists explicitly, so necessity verifies all Hall inequalities at once. In the modified instance, $S=\{a,b,c\}$ has $N(S)=\{1,2\}$, certifying failure.

Exercise. Let the three acceptable sets be $\{x\}$, $\{x,y\}$, and $\{y,z\}$. Find a complete assignment. Hint: start with the singleton list. Answer: assign $x,y,z$ respectively; its distinct representatives also certify Hall's condition.

12.2 SDRs and transversals

Let $(A_i)_{i\in I}$ be a finite indexed family of finite sets. The indices matter: two different indices may have identical sets. A system of distinct representatives, or SDR, chooses $r_i\in A_i$ for every $i\in I$, with all $r_i$ different. Its image $T=\{r_i:i\in I\}$ is a transversal: a set of $|I|$ elements that can be assigned bijectively to the indexed sets, with each assigned element belonging to its set. Merely meeting every set does not suffice.

Construct a bipartite graph whose left vertices are the indices and whose right vertices are the elements of $\bigcup_i A_i$. Join $i$ to $r$ exactly when $r\in A_i$. An SDR is precisely a matching saturating the index side. Hall's theorem becomes

$$\left|\bigcup_{i\in J}A_i\right|\ge |J| \qquad\text{for every }J\subseteq I.$$

A partial SDR makes these choices for only a subset of the indices. It can be enlarged by an augmenting path that reassigns previously chosen representatives. This explains why committing permanently to the first acceptable element is unreliable.

For example, $A_1=A_2=\{r\}$ gives no SDR: the sets are nonempty, but two indexed demands compete for one element. The one-element set $\{r\}$ meets both sets, yet is not a transversal for this two-index family.

Exercise. Does $A_1=\{r\}$, $A_2=\{r\}$, $A_3=\{s,t\}$ have an SDR? Hint: the full union has size three, so inspect a smaller index set. Answer: no; $J=\{1,2\}$ has a union of size one.

12.3 Stable matchings and Gale–Shapley

Acceptability determines whether an assignment is allowed. Stability also uses rankings. For this section, take two sets $L,R$ of the same finite size $n$. Each participant strictly ranks every member of the other side, with no ties, and every pair is acceptable. A blocking pair for a perfect matching is an unmatched pair whose members both prefer each other to their current partners. A matching is stable if it has no blocking pair.

The Gale–Shapley deferred-acceptance procedure constructs one. Initially nobody is held. Each free proposer approaches their highest-ranked receiver not yet approached. A receiver keeps the best proposer seen so far and rejects the others, including a previously held proposer if a better one arrives. Repeat until no proposer is free. A held proposal is provisional.

There are at most $n^2$ proposals, because no pair repeats. A free proposer cannot have exhausted every receiver: all receivers would then hold distinct proposers, leaving nobody free. Hence termination gives a perfect matching. If a proposer prefers some receiver to their final partner, they approached that receiver earlier and were rejected. Receivers' held partners only improve, so that receiver cannot prefer this proposer to their final partner. Thus no blocking pair exists. This is the central existence argument in Gale and Shapley's original paper. math.utoronto.ca

Here is a complete three-by-three example. A ranking lists the most preferred partner first.

In round one, $a,b$ propose to $x$, and $c$ proposes to $y$. Receiver $x$ holds $b$ and rejects $a$; $y$ holds $c$. Then $a$ proposes to $y$, which replaces $c$ by $a$. Next $c$ proposes to $x$ and is rejected. Finally $c$ proposes to $z$. The result is $\{(a,y),(b,x),(c,z)\}$ after six proposals.

To check stability directly, $b$ has their first choice. Applicant $a$ prefers only $x$ to $y$, but $x$ prefers its partner $b$ to $a$. Applicant $c$ prefers $y$ and $x$ to $z$, but those receivers prefer their respective partners $a$ and $b$ to $c$. These are all potential blocking pairs.

The diagram records the preferences and the held pairs after each round. Arrows between cards indicate chronological progression; proposal and rejection labels specify each change.

Exercise. Take $a:x,y$ and $b:y,x$, with receiver rankings $x:b,a$ and $y:a,b$. Run the procedure with each side proposing. Hint: all first proposals go to different participants. Answer: applicant proposals give $a$–$x$, $b$–$y$; receiver proposals give $a$–$y$, $b$–$x$. Both are stable, so stability need not determine a unique assignment. The complete strict-ranking model was essential to the existence proof given here; incomplete lists and ties require their own conventions.

12.4 Kőnig's theorem

A vertex cover is a set of vertices containing at least one endpoint of every edge. Think of it as placing security guards at street intersections: a guard at an intersection can observe every street (edge) touching that intersection, and a valid vertex cover ensures every single street in the city is watched. Real-world applications include placing network monitoring nodes, optimizing camera placement in security systems, and minimizing staff needed to supervise pairs of compatible tasks.

Let $\nu(G)$ denote maximum matching size and $\tau(G)$ minimum vertex-cover size. Kőnig's theorem states that for every finite bipartite graph,

$$ \nu(G)=\tau(G). $$

These are cardinalities, not weights. The graph terminology introduced here is sufficient; the course roadmap lists the planned fuller treatment in section 15.1.

For any graph, $\nu(G)\le\tau(G)$: each edge of a matching needs a covering vertex, and distinct matching edges cannot use the same vertex. To prove equality in the bipartite case, choose a maximum matching $M$. Use the directed edges from section 12.1, now starting the reachability search from all unmatched vertices of $L$. Write the reached sets as $Z_L,Z_R$, and set

$$ C=(L\setminus Z_L)\cup Z_R. $$

This is a cover. An uncovered edge would join $u\in Z_L$ to $v\notin Z_R$. If it is unmatched, its direction makes $v$ reachable. If it is matched, a reached matched applicant was reached through its matched partner, so $v$ was already reached. Both possibilities contradict the assumed locations.

Every reached receiver is matched, since otherwise an augmenting path exists. All unmatched applicants are reached by initialization. On a matched edge, either both endpoints are reached or neither is: reachability passes from its receiver to its applicant, and a reached matched applicant brings its partner with it. The cover therefore takes exactly one endpoint of each matched edge and no unmatched vertices. Thus $|C|=|M|$, proving equality.

For the modified motivating instance, $a,b,c$ accept $\{1,2\}$ and $d$ accepts $\{3,4\}$. The matching $\{(a,1),(b,2),(d,3)\}$ has size three. Starting from unmatched $c$ reaches $a,b,c$ and slots $1,2$. The constructed cover is $\{d,1,2\}$, also of size three. Exhibiting this matching and cover proves both are optimal without inspecting every matching.

“Maximum” and “maximal” differ. A maximal matching cannot be enlarged just by adding an edge; a maximum matching has the largest possible size. In the four-vertex path with edges $12,23,34$, the single middle edge is maximal, but the two outer edges form a larger matching.

Exercise. For that path, give a maximum matching and a minimum cover. Hint: a cover can use the two middle vertices. Answer: $\{12,34\}$ and $\{2,3\}$, each of size two.

12.5 Tutte's matching theorem

Optional extension. This section is not required for the chapter foundation. In previous sections, we only considered bipartite graphs—systems divided cleanly into two distinct sets like applicants and job slots. Now, we expand our view to general graphs, where edges can connect any pair of vertices in a single population.

Real-world applications of general graph matchings include pairing players in a chess tournament, connecting peer-to-peer network nodes, pairing wireless devices via Bluetooth, and organizing kidney donor exchange chains. In these symmetric domains, anyone can potentially pair with anyone else, so the bipartite split no longer applies.

To analyze matchings in general graphs, we look at what happens when a subset of vertices $S$ is removed. A connected component is a maximal set of vertices joined by paths; an isolated vertex is a one-vertex component. For $S\subseteq V(G)$, write $G-S$ for the graph obtained by deleting those vertices and their incident edges. Let $o(G-S)$ count its components with an odd number of vertices. Sections 15.1 and 15.3 on the course roadmap develop graphs and connectivity further.

Tutte's theorem provides a necessary and sufficient condition for general graphs to possess a perfect matching, expanding Hall's marriage theorem beyond bipartite structures:

Tutte's theorem says that a finite undirected simple graph has a perfect matching exactly when

$$ o(G-S)\le |S|\qquad\text{for every }S\subseteq V(G). $$

Why Necessity Holds (The Parity Bottleneck): Internal matching edges can only cover vertices of a component in pairs. Therefore, every component with an odd number of vertices will always have at least one leftover "orphan" vertex that cannot be paired internally. To achieve a perfect matching, every such orphan must be paired with a distinct vertex in $S$. Since a matching edge cannot reuse an endpoint, set $S$ must contain at least as many vertices as there are odd components. Thus, $o(G-S) \le |S|$ is strictly necessary for every $S \subseteq V(G)$.

For example, the star with center $v$ and three leaves has four vertices, but deleting $S=\{v\}$ leaves three odd components. Since $3>1$, no perfect matching exists. Its maximum matching has only one edge. An even vertex count alone is insufficient.

Sufficiency mechanism—proof outline. Induct on the even number of vertices, with the empty graph as the base. The condition at $S=\varnothing$ forces even component sizes. If there is no nonempty tight set with $o(G-S)=|S|$, parity strengthens the inequalities to $o(G-S)\le|S|-2$ for nonempty $S$. Delete the endpoints of any edge; the remaining graph satisfies Tutte's condition, so induction completes the matching.

Otherwise choose a largest tight set $S$. Its remaining components are odd: an even component would allow one more vertex to be added to $S$ while preserving equality. Maximality and parity imply that deleting any one vertex from an odd component leaves a graph satisfying Tutte's condition. Induction therefore matches its remaining vertices. Finally, Hall's theorem pairs the vertices of $S$ with distinct odd components to which they are adjacent; a shortage would itself violate Tutte's condition. Choose those connecting edges and complete the internal matchings. The component-inequality details are omitted in this outline; a full induction appears in Mary Radcliffe's matching lecture notes. math.cmu.edu

A four-cycle has the perfect matching consisting of two opposite edges, so the necessity argument verifies every Tutte inequality for it. This illustrates the theorem's two kinds of certificate: a perfect matching establishes success, while one violating set $S$ establishes failure.

Exercise. Can two disjoint triangles have a perfect matching? Hint: try $S=\varnothing$. Answer: no; there are two odd components, giving $o(G)=2>0$, despite six vertices in total.

12.6 Perfect matchings and the permanent

While Hall's theorem answers the decision problem of whether a perfect matching exists, the permanent answers the counting problem of how many distinct perfect matchings exist. In a bipartite graph with equal side sizes $|L|=|R|=n$, every perfect matching corresponds to selecting $n$ non-overlapping edges that cover all vertices on both sides.

Applications & Significance: Counting perfect matchings is fundamental across multiple scientific fields:

• Statistical Physics & Chemistry: The "dimer problem" counts how many ways a crystal lattice or molecular grid (e.g., benzenoid hydrocarbons) can be completely covered by two-atom tiles (Kekulé structures).
• Quantum Computing & Boson Sampling: Computing the permanent of transition matrices dictates photon interference patterns in quantum optics experiments.
• Network Reliability & Diversity: Measures the fault tolerance and number of alternative optimal routing configurations in task-allocation networks.

Index both sides by $1,\ldots,n$ and form the $0$–$1$ matrix $A=(a_{ij})$, where $a_{ij}=1$ means the pair $(i,j)$ is allowed. A perfect matching chooses one entry in each row and each column, all equal to one. Thus

$$ \operatorname{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^{n}a_{i,\sigma(i)} $$

counts perfect matchings. Here $S_n$ is the set of permutations of the column indices. Unlike a determinant, the permanent attaches no permutation signs.

For example,

$$ A=\begin{pmatrix}1&1&0\\1&1&1\\0&1&1\end{pmatrix} $$

has three allowed permutations, written as the column choices in row order: $(1,2,3)$, $(2,1,3)$, and $(1,3,2)$. Hence $\operatorname{per}(A)=3$, whereas $\det A=-1$. For the two-by-two all-ones matrix, the distinction is even sharper: the permanent is two and the determinant is zero.

Inclusion–exclusion gives a useful alternative formula. Write $[n]=\{1,\ldots,n\}$. For $T\subseteq[n]$, the product of row sums counts assignments choosing an allowed column in $T$ for each row, with repetitions permitted. Excluding assignments missing any column gives

$$ \operatorname{per}(A)= \sum_{T\subseteq[n]}(-1)^{n-|T|} \prod_{i=1}^{n}\left(\sum_{j\in T}a_{ij}\right). $$

Using all $n$ columns in an assignment of $n$ rows forces every column to occur once. This proves the formula, commonly called Ryser's formula, directly from the preceding chapter's sieve principle. Ryser's formula reduces computing time from $O(n \cdot n!)$ brute-force search to $O(n 2^n)$, making it the standard algorithm for exact permanent calculation.

For the displayed three-by-three matrix, singleton subsets contribute $1$ in total; two-column subsets have products $4,2,4$ and contribute $-10$; the full column set contributes $2\cdot3\cdot2=12$. The empty subset contributes zero. The result is $1-10+12=3$.

The interpretation uses the bipartite incidence matrix. Applying the permanent to the ordinary adjacency matrix of a general graph instead counts permutations with allowed directed transitions; these need not be matchings (they represent cycle covers).

Exercise. Apply the subset formula to the two-by-two all-ones matrix. Hint: the full column set contributes four. Answer: $4-1-1=2$.

12.7 Matching polynomials

Optional extension. While an algorithm or condition tells us whether a matching of a specific size exists, matching polynomials act as a unified algebraic "fingerprint" for a graph. They encode the complete distribution of matching sizes—from the empty matching up to maximum or perfect matchings—into a single mathematical function.

What, Why, and Applications:

• What: A matching polynomial is a generating function where the coefficient of $t^k$ or $x^{n-2k}$ counts the number of valid matchings containing exactly $k$ edges.
• Why: Algebraic operations on polynomials (such as differentiation or factorisation) reveal structural properties of the graph, such as total matching counts, independence numbers, and network connectivity.
• Applications: In statistical mechanics and chemistry, matching polynomials model the monomer-dimer problem (predicting how molecules or gas particles adsorb onto crystal surfaces) and determine the topological resonance energy of organic molecules like benzene.

For a finite simple graph $G$ with $n$ vertices, let $m_k(G)$ be the number of matchings with $k$ edges, with $m_0(G)=1$ for the empty matching. Define the matching generating polynomial

$$ Z_G(t)=\sum_{k=0}^{\lfloor n/2\rfloor}m_k(G)t^k $$

and the conventional signed matching polynomial

$$ \mu_G(x)=\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^km_k(G)x^{n-2k}. $$

These use the same counts but different signs and exponents. For the four-vertex path with edges $12,23,34$, there is one empty matching, three one-edge matchings, and one two-edge matching $\{12,34\}$. Therefore

$$ Z_G(t)=1+3t+t^2,\qquad \mu_G(x)=x^4-3x^2+1. $$

For an edge $e=uv$, partition matchings according to whether they contain it. Those omitting it are matchings of $G-e$. Those containing it cannot use another edge incident with $u$ or $v$; deleting these endpoints leaves an arbitrary matching of $G-\{u,v\}$. Thus

$$ Z_G(t)=Z_{G-e}(t)+tZ_{G-\{u,v\}}(t), $$

and, accounting for the extra edge's sign,

$$ \mu_G(x)=\mu_{G-e}(x)-\mu_{G-\{u,v\}}(x). $$

The empty graph has both polynomials equal to one. Adding an isolated vertex leaves $Z_G$ unchanged and multiplies $\mu_G$ by $x$. For disjoint graphs, both polynomials multiply, because a matching is chosen independently in each component.

For the four-vertex path, remove the middle edge. The remaining two disjoint edges give $Z_{G-e}=(1+t)^2$; deleting its two endpoints leaves two isolated vertices, whose generating polynomial is one. Hence $Z_G=(1+t)^2+t$, agreeing with direct enumeration. When $n$ is even, $m_{n/2}(G)$ counts perfect matchings; when $n$ is odd, none can exist.

Exercise. Find both polynomials for a triangle. Hint: any two edges share a vertex. Answer: $Z_G(t)=1+3t$ and $\mu_G(x)=x^3-3x$.

12.8 Fractional matchings and matching polyhedra

Optional extension. This section introduces a graduate-level viewpoint without requiring prior linear programming. A linear inequality bounds a weighted sum of variables; a polyhedron is the set satisfying finitely many such inequalities. A bounded polyhedron is a polytope. A convex combination is an average with nonnegative coefficients summing to one. See the course roadmap for planned sections 39.1 on linear programming and 39.4 on duality.

What, Why, and Applications:

• What: A fractional matching relaxes the integer requirement $x_e \in \{0, 1\}$ to real numbers $x_e \in [0, 1]$. Each edge receives a weight representing the fraction of time or capacity allocated to that connection.
• Why: Integer optimization problems (like finding maximum matchings) are hard in general, whereas continuous Linear Programs (LPs) can be solved efficiently. Fractional matchings provide a relaxed upper bound on graph capacity.
• Applications: Used extensively in network routing (time-sharing bandwidth), fractional job scheduling on servers, and game theory (fractional core solutions in cooperative markets).

For each edge $e$, assign a real number $x_e\ge0$. A fractional matching satisfies

$$ \sum_{e\ni v}x_e\le1\qquad\text{for every vertex }v. $$

Each edge allocation consumes capacity at both endpoints. A genuine matching corresponds to its incidence vector: $x_e=1$ on selected edges and zero elsewhere. Maximizing $\sum_e x_e$ over fractional matchings relaxes the maximum-cardinality matching problem. The feasible set is bounded because each coordinate lies between zero and one.

For a triangle, assigning $1/2$ to each of its three edges satisfies every vertex constraint and has total $3/2$. A genuine matching has at most one edge. Thus the basic inequalities can allow a larger fractional value.

In a bipartite graph, however, every extreme point of this feasible polytope is integral. An extreme point cannot be expressed as the midpoint of two different feasible points. Here is the perturbation proof. Suppose some coordinates lie strictly between zero and one, and retain just these fractional edges. If their graph contains a cycle, bipartiteness makes that cycle even; alternately add and subtract a sufficiently small $\varepsilon$ along it. Vertex sums stay unchanged, and both perturbation directions remain feasible.

If the fractional-edge graph has no cycle, a component containing an edge is a finite tree. Choose a path between two leaves and alternate the perturbations along it. Internal vertex sums stay fixed. At a leaf, the only positive incident coordinate is its fractional edge: a coordinate equal to one cannot coexist with a positive fractional edge. Its sum is therefore strictly below one, giving room for either perturbation direction. A small enough $\varepsilon$ preserves nonnegativity and endpoint capacity. In both cases the original point is the midpoint of two distinct feasible points, contradicting extremality.

Using the elementary polytope fact that a bounded polyhedron is the convex hull of its extreme points, this proves that bipartite fractional matchings are convex combinations of genuine matchings. In a four-cycle, the vector with value $1/2$ on every edge is explicitly the average of its two opposite-edge perfect matchings. A fractional vector can exist without itself being an extreme point.

For a general graph, let $E(S)$ denote edges with both endpoints in $S$. Every genuine matching satisfies the additional odd-set inequalities

$$ \sum_{e\in E(S)}x_e\le\frac{|S|-1}{2} \qquad\text{whenever }|S|\text{ is odd}. $$

An odd group cannot pair all its vertices internally. Edmonds' matching-polyhedron theorem states that nonnegativity, vertex-capacity inequalities, and these odd-set inequalities describe exactly the convex hull of matching incidence vectors. The necessity just explained is elementary; the general sufficiency theorem is stated here without proof. See Edmonds' original matching-polyhedron paper. nvlpubs.nist.gov For the triangle, taking all three vertices as $S$ adds $x_{12}+x_{23}+x_{31}\le1$, excluding the half-edge vector.

There is a direct connection to Hall. In a bipartite graph, suppose a fractional matching saturates each applicant, meaning its incident allocations sum to one. For any $S\subseteq L$, all that allocation goes into $N(S)$, whose slots each have capacity at most one. Therefore

$$ |S|=\sum_{a\in S}\sum_{r\in N(S)}x_{ar}\le |N(S)|, $$

where nonexistent edges have allocation zero. Hall's theorem then gives a genuine matching saturating $L$. Conversely, such a matching is itself a fractional solution. Fractional allocation cannot bypass a Hall bottleneck.

Exercise. Three applicants accept only two slots. Could splitting each applicant's allocation between slots saturate everyone? Hint: sum the two slot-capacity inequalities. Answer: no; the applicants require total three, while the slots permit total at most two.

Produce a matching or a certificate that one cannot exist

An assignment system should explain its result. For success, list one distinct acceptable slot for every applicant. For failure, give a group $S$ and its complete neighborhood, with $|N(S)|<|S|$. To certify a maximum partial matching, give a matching and a vertex cover of the same size. These certificates can be checked directly without trusting the search procedure.

This framework models assigning jobs to compatible machines for one time interval, with each job and machine used at most once. Hall detects simultaneous capacity shortages. A fractional model permits divisible allocation, but summing capacities shows that the same Hall shortages remain. If rankings rather than just compatibility matter, stability adds a separate requirement studied by deferred acceptance.