## Bipartite matchings via linear programming

An important tool for combinatorial optimisation problems, and graph problems among them, is linear programming, a method (and a problem) to find the optimum of a linear function on a polyhedron (i.e. on an intersection of half-spaces.) Often, such an intersection is bounded, and then one talks about a (convex) polytope rather than a polyhedron.
The optimum of a linear function on a polytope $P$ is always reached on a vertex, or, more generally, on a set of vertices of $P$ generating an optimal face. (A vertex is a point in $P$ that cannot be written as a nontrivial convex combination of two other points of $P.$)

Here we demonstrate a way to encode the problem of finding the size of a maximum matching (or, more generally, the maximum weight of a matching) in a bipartite graph $\Gamma=(V,E)$ as a linear programming problem.

As a warmup, we treat perfect matchings. Consider the vector of $|E|$ variables $x=(x_{e_1},x_{e_2}...),$ and the system of inequalities

$x_e\geq 0,\ e\in E,\quad \sum_{v\in e\in E} x_e=1,\ v\in V,\qquad (*)$

Certainly, if $x=x_M$ is the characteristic vector of a perfect matching $M$ of $\Gamma,$ i.e. $x$ is a 0-1 vector with 1s corresponding to the edges of $M,$ it satisfies the system $(*)$ above. Thus maximizing the linear function $\sum_{e\in E} w_e x_e$ on the polytope defined by $(*)$ gives an upper bound on the size of a maximum weight perfect matching in $\Gamma$ w.r.t. the edge weights $w_e, e\in E.$
But in fact much more holds: namely, this bound is tight, as follows from the following theorem.

For a bipartite graph $\Gamma,$ the vertices of the polytope $P$ defined by $(*)$ have 0-1 coordinates, and are in the one-to-one correspondence with the perfect matchings of $\Gamma.$

Proof. Let $x$ be a vertex of $P,$ and $X$ be the support of $x,$ i.e. $X=\{e\in E\mid x_e> 0\}.$ Then $X$ does not contain a cycle. Indeed, a cycle in $X$ can be decomposed into the disjoint union of two (not necessarily perfect) matchings, say $M$ and $N,$ as $\Gamma$ is bipartite and so each cycle in $\Gamma$ is even. Observe that $\sum_{v\in e\in E} ((x_M)_e-(x_N)_e)=0$ for any $v\in V.$
Thus there exists $\epsilon>0$ such that $x\pm\epsilon(x_M-x_N)\in P,$ and so $2x=(x+\epsilon(x_M-x_N))+(x-\epsilon(x_M-x_N))),$ contradicting the assumption that $x$ is a vertex (and so it cannot be a convex combination of two points in $P$).

Thus $X$ is a forest. Let $e\in X$ be a leaf of a subtree of $X.$ Then $(*)$ implies that $x_e=1.$ Therefore any connected component of $X$ is an edge, and so $X$ is a matching. It is a perfect matching by $(*).$ QED.

By this theorem, the maximum of $\sum_{e\in E} w_e x_e$ on $P$ is reached on a perfect matching $x=x_M.$ Another almost immediate corollary is the following well-known result on doubly stochastic matrices (an $n\times n$ nonnegative real matrix is called doubly stochastic if its row and column sums are equal to 1.)

A doubly stochastic matrix is a convex combination of permutation matrices.

Indeed, $n\times n$-permutation matrices (the 0-1 doubly stochastic matrices) are in one-to-one correspondence to the perfect matchings of $K_{n,n},$ (the characteristic vector of such a matching can be viewed as an $n\times n$ matrix, with rows corresponding to one part of the graph, and columns to the other) and so the doubly stochastic matrices are exactly the points of the perfect matching polytope of $K_{n,n},$ that has, by our theorem, perfect matchings as vertices (and so any point in it is a convex combination of perfect matchings).

Excercise. Formulate an analogy of system $(*)$ for matchings (not necessarily perfect) in bipartite graphs, and prove the corresponding result for vertices of the polytope in question. Using it, formulate the linear programming problem with optimal value being the size of maximum matching.

Excercise. Show that these constructions fail for non-bipartite graphs.