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.[1]^:273–285

Preliminaries

Incidence vectors and matrices

Let G = (V, E) be a graph with n = |V| nodes and m = |E| edges.

For every subset U of vertices, its incidence vector 1_U 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 1_F 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(v). Therefore, the vector 1_E(V) 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 A_G, is an n-by-m matrix in which each row v is the incidence vector 1_E(V). 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 cycle of length 3), a square graph (a cycle of length 4), and the complete graph on 4 vertices.

${\displaystyle {\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\1&0&0&1\\\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0&1&0\\0&1&1&0&0&1\\0&0&1&1&1&0\\1&0&0&1&0&1\\\end{pmatrix}}}$

Linear programs

For every subset F of edges, the dot product 1_E(v) · 1_F represents the number of edges in F that are adjacent to v. Therefore, the following statemens are equivalent:

• A subset F of edges represents a matching in G;
• For every node v in V: 1_E(v) · 1_F ≤ 1.
• A_G · 1_F ≤ 1_V.

The cardinality of a set F of edges is the dot product 1_E · 1_{F .} Therefore, a maximum cardinality matching in G is given by the following integer linear program:

Maximize 1_E · x

Subject to: x in {0,1}^m

__________ A_G · x ≤ 1_V.

Fractional matching polytope

The fractional matching polytope of a graph G, denoted FMP(G), 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 1_E · x

Subject to: x ≥ 0_E

__________ A_G · x ≤ 1_V.

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 x₁+x₂+x₃

Subject to: x₁≥0, x₂≥0, x₃≥0_.

__________ x₁+x₂≤1, x₂+x₃≤1, x₃+x₁≤1.

This set of inequalities represents a polytope in R³ - the 3-dimensional Euclidean space.

The polytope has five corners (extreme points). These are the points that attain equality in 3 out of the 6 defining inequalities. The corners are (0,0,0), (1,0,0), (0,1,0), (0,0,1), and (1/2,1/2,1/2).[2] The first corner (0,0,0) represents the trivial (empty) matching. The next three corners (1,0,0), (0,1,0), (0,0,1) represent the three matchings of size 1. The fifth corner (1/2,1/2,1/2) 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 R⁴. The corners of this polytope are (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,0,1,0), (0,1,0,1). 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 (usually called just the matching polytope) of a graph G, denoted MP(G), is a polytope whose corners are the incidence vectors of the integral matchings in G.

MP(G) is always contained in FMP(G). In the above examples:

• The MP of the triangle graph is strictly contained in its FMP, since the MP does not contain the non-integral corner (1/2, 1/2, 1/2).
• The MP of the 4-cycle graph is identical to its FMP, since all the corners of the FMP are integral.

The matching polytopes in a bipartite graph

The above example is a special case of the following general theorem:[1]^:274

G is a bipartite graph if-and-only-if MP(G) = FMP(G) if-and-only-if all corners of FMP(G) have only integer coordinates.

This theorem can be proved in several ways.

Proof using matrices

When G is bipartite, its incidence matrix A_G 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 (which we denote by K). The base k = 1 follows from the definition of A_G - every element in it is either 0 or 1. For k>1 there are several cases:

• If K has a column consisting only of zeros, then det K = 0.
• If K has a column with a single 1, then det K can be expanded about this column and it equals either +1 or -1 times a determinant of a (k − 1) by (k − 1) matrix, which by the induction assumption is 0 or +1 or −1.
• Otherwise, each column in K has two 1s. Since the graph is bipartite, the rows can be partitioned into two subsets, such that in each column, one 1 is in the top subset and the other 1 is in the bottom subset. This means that the sum of the top subset and the sum of the bottom subset are both equal to 1_E minus a vector of |E| ones. This means that the rows of K are linearly dependent, so det K = 0.

As an example, in the 4-cycle (which is bipartite), the det A_G = 1. In contrast, in the 3-cycle (which is not bipartite), det A_G = 2.

Each corner of FMP(G) 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 A_G. 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(G) = MP(G).

Proof using the definition of extreme points

A corner (= extreme point) 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(G). Let x_e be some non-integral element of it (corresponding to an edge e with non-integral weight). It is possible to increase x_e 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_- (x = (x₊ + x_-)/2), 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 (d − 1)-dimensional. For any graph G, the facets of MP(G) are given by the following inequalities:[1]^:275–279

• x ≥ 0_E
• 1_E(v) · x ≤ 1 (where v is a non-isolated vertex such that, if v has only one neighbor u, then {u,v} is a connected component of G, and if v has exactly two neighbors, then they are not adjacent).
• 1_E(S) · x ≤ (|S| − 1)/2 (where S spans a 2-connected factor-critical subgraph.)

Perfect matching polytope

The perfect matching polytope of a graph G, denoted PMP(G), is a polytope whose corners are the incidence vectors of the integral perfect matchings in G.[1]^:274 Obviously, PMP(G) is contained in MP(G); In fact, PMP(G) is the face of MP(G) determined by the equality:

1_E · x = n/2.

See also

• Stable matching polytope

References

1. Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
2. "1 Bipartite Matching Polytope, Stable Matching Polytope x1 x2 x3 Lecture 10: Feb ppt download". slideplayer.com. Retrieved 2020-07-17.

External links

• The matching polytope, by Michael Goemans
• The matching polytope, by Jan Vondrak
• The matching polytope, by Vincent Jost