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'' = (''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, each 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.

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 statements 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 ''^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). 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:

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'').

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:

* 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 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.{{Rp, 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

External links

The matching polytope, by Michael Goemans

The matching polytope, by Jan Vondrak

The matching polytope, by Vincent Jost

Matching (graph theory)
Polytopes