Matching polytope


In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the theory of matching.

Preliminaries

Incidence vectors and matrices

Let G = be a graph with n = |V| nodes and m = |E| edges.
For every subset U of vertices, its incidence vector 1U is a vector of size n, in which element v is 1 if node v is in U, and 0 otherwise. Similarly, for every subset F of edges, its incidence vector 1F is a vector of size m, in which element e is 1 if edge e is in F, and 0 otherwise.
For every node v in V, the set of edges in E adjacent to v is denoted by E. Therefore, the vector 1E is a 1-by-m vector in which element e is 1 if edge e is adjacent to v, and 0 otherwise. The incidence matrix of the graph, denoted by AG, is an n-by-m matrix in which each row v is the incidence vector 1E. In other words, each element v,e in the matrix is 1 if node v is adjacent to edge e, and 0 otherwise.
Below are three examples of incidence matrices: the triangle graph, a square graph, and the complete graph on 4 vertices.

Linear programs

For every subset F of edges, the dot product 1E · 1F represents the number of edges in F that are adjacent to v. Therefore, the following statemens are equivalent:
The cardinality of a set F of edges is the dot product 1E · 1F . Therefore, a maximum cardinality matching in G is given by the following integer linear program:
Maximize 1E · x
Subject to: x in m
__________ AG · x ≤ 1V.

Fractional matching polytope

The fractional matching polytope of a graph G, denoted FMP, is the polytope defined by the relaxation of the above linear program, in which each x may be a fraction and not just an integer:
Maximize 1E · x
Subject to: x ≥ 0E
__________ AG · x ≤ 1V.
This is a linear program. It has m "at-least-0" constraints and n "less-than-one" constraints. The set of its feasible solutions is a convex polytope. Each point in this polytope is a fractional matching. For example, in the triangle graph there are 3 edges, and the corresponding linear program has the following 6 constraints:
Maximize x1+x2+x3
Subject to: x1≥0, x2≥0, x3≥0.
__________ x1+x2≤1, x2+x3≤1, x3+x1≤1.
This set of inequalities represents a polytope in R3 - the 3-dimensional Euclidean space.
The polytope has five corners. These are the points that attain equality in 3 out of the 6 defining inequalities. The corners are,,,, and. The first corner represents the trivial matching. The next three corners,, represent the three matchings of size 1. The fifth corner does not represent a matching - it represents a fractional matching in which each edge is "half in, half out". Note that this is the largest fractional matching in this graph - its weight is 3/2, in contrast to the three integral matchings whose size is only 1.
As another example, in the 4-cycle there are 4 edges. The corresponding LP has 4+4=8 constraints. The FMP is a convex polytope in R4. The corners of this polytope are,,,,,,. Each of the last 2 corners represents matching of size 2, which is a maximum matching. Note that in this case all corners have integer coordinates.

Integral matching polytope

The integral matching polytope of a graph G, denoted MP, is a polytope whose corners are the incidence vectors of the integral matchings in G.
MP is always contained in FMP. In the above examples:
The above example is a special case of the following general theorem:
G is a bipartite graph if-and-only-if MP = FMP if-and-only-if all corners of FMP have only integer coordinates.
This theorem can be proved in several ways.

Proof using matrices

When G is bipartite, its incidence matrix AG is totally unimodular - every square submatrix of it has determinant 0, +1 or 1. The proof is by induction on k - the size of the submatrix. The base k = 1 follows from the definition of AG - every element in it is either 0 or 1. For k>1 there are several cases:
As an example, in the 4-cycle, the det AG = 1. In contrast, in the 3-cycle, det AG = 2.
Each corner of FMP satisfies a set of m linearly-independent inequalities with equality. Therefore, to calculate the corner coordinates we have to solve a system of equations defined by a square submatrix of AG. By Cramer's rule, the solution is a rational number in which the denominator is the determinant of this submatrix. This determinant must by +1 or −1; therefore the solution is an integer vector. Therefore all corner coordinates are integers.
By the n "less-than-one" constraints, the corner coordinates are either 0 or 1; therefore each corner is the incidence vector of an integral matching in G. Hence FMP = MP.

Proof using the definition of extreme points

A corner of a polytope is, by definition, a point that is not the mid-point of any two different points of the polytope. Let x be a non-integral point of FMP. Let xe be some non-integral element of it. It is possible to increase xe by some small number ε, decrease edges of adjacent vertices by ε, increase edges of adjacent vertices by ε, etc., such that we modify the weights of all edges in a cycle. Since G is bipartite, the cycle has even length, and therefore the total weight near each vertex of the cycle has not changed. Thus we get a new point x+ which is the same as x up to adding/removing ε from edges of an even cycle. Similarly, by inverting the sign of the additions, we get a new point x-. Now, x is the midpoint of x+ and x-, so it cannot be a corner.

The facets of the matching polytope

A facet of a polytope is the set of its points which satisfy an essential defining inequality of the polytope with equality. If the polytope is d-dimensional, then its facets are -dimensional. For any graph G, the facets of MP are given by the following inequalities:
The perfect matching polytope of a graph G, denoted PMP, is a polytope whose corners are the incidence vectors of the integral perfect matchings in G. Obviously, PMP is contained in MP; In fact, PMP is the face of MP determined by the equality:
1E · x = n/2.