Fractional matching

In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.

Definition

Given a graph G = (V, E), a fractional matching in G is a function that assigns, to each edge e in E, a fraction f(e) in [0, 1], such that for every vertex v in V, the sum of fractions of edges adjacent to v is at most 1:[1]

$${\displaystyle \forall v\in V:\sum _{e\ni v}f(e)\leq 1}$$

A matching in the traditional sense is a special case of a fractional matching, in which the fraction of every edge is either 0 or 1: f(e) = 1 if e is in the matching, and f(e) = 0 if it is not. For this reason, in the context of fractional matchings, usual matchings are sometimes called integral matchings.

The size of an integral matching is the number of edges in the matching, and the matching number ${\displaystyle \nu (G)}$ of a graph G is the largest size of a matching in G. Analogously, the size of a fractional matching is the sum of fractions of all edges. The fractional matching number of a graph G is the largest size of a fractional matching in G. It is often denoted by ${\displaystyle \nu ^{*}(G)}$.[2] Since a matching is a special case of a fractional matching, for every graph G one has that the integral matching number of G is less than or equal to the fractional matching number of G; in symbols:

$${\displaystyle \nu (G)\leq \nu ^{*}(G).}$$

A graph in which ${\displaystyle \nu (G)=\nu ^{*}(G)}$ is called a stable graph.[3] Every bipartite graph is stable; this means that in every bipartite graph, the fractional matching number is an integer and it equals the integral matching number.

In a general graph, ${\displaystyle \nu (G)>{\frac {2}{3}}\nu ^{*}(G).}$ The fractional matching number is either an integer or a half-integer. [4]

Matrix presentation

For a bipartite graph G = (X+Y, E), a fractional matching can be presented as a matrix with |X| rows and |Y| columns. The value of the entry in row x and column y is the weight on the edge (x,y).

Perfect fractional matching

A fractional matching is called perfect if the sum of weights adjacent to each vertex is exactly 1. The size of a perfect matching is exactly |V|/2.

In a bipartite graph G = (X+Y, E), a fractional matching is called X-perfect if the sum of weights adjacent to each vertex of X is exactly 1. The size of an X-perfect fractional matching is exactly |X|.

For a bipartite graph G = (X+Y, E), the following are equivalent:

• G admits an X-perfect integral matching,
• G admits an X-perfect fractional matching, and
• G satisfies the condition to Hall's marriage theorem.

The first condition implies the second because an integral matching is a fractional matching. The second implies the third because, for each subset W of X, the sum of weights near vertices of W is |W|, so the edges adjacent to them are necessarily adjacent to at least |W| vertices of Y. By Hall's marriage theorem, the last condition implies the first one.[5]

Algorithmic aspects

A largest fractional matching in a graph can be easily found by linear programming, or alternatively by a maximum flow algorithm. In a bipartite graph, it is possible to convert a maximum fractional matching to a maximum integral matching of the same size. This leads to a simple polynomial-time algorithm for finding a maximum matching in a bipartite graph.[6]

If G is a bipartite graph with |X| = |Y| = n, and M is a perfect fractional matching, then the matrix representation of M is a doubly stochastic matrix - the sum of elements in each row and each column is 1. Birkhoff's algorithm can be used to decompose the matrix into a convex sum of at most n²-2n+2 permutation matrices. This corresponds to decomposing M into a convex sum of at most n²-2n+2 perfect matchings.

Fractional matching polytope

Given a graph G = (V,E), the fractional matching polytope of G is a convex polytope that represents all possible fractional matchings of G. It is a polytope in R^|E| - the |E|-dimensional Euclidean space. Each point (x₁,...,x_|E|) in the polytope represents a matching in which the weight of each edge e is x_e. The polytope is defined by |E| non-negativity constraints (x_e ≥ 0 for all e in E) and |V| vertex constraints (the sum of x_e, for all edges e that are adjacent to a vertex v, is at most 1).

References

1. Aharoni, Ron; Kessler, Ofra (1990-10-15). "On a possible extension of Hall's theorem to bipartite hypergraphs". Discrete Mathematics. 84 (3): 309–313. doi:10.1016/0012-365X(90)90136-6. ISSN 0012-365X.
2. Liu, Yan; Liu, Guizhen (2002). "The fractional matching numbers of graphs". Networks. 40 (4): 228–231. doi:10.1002/net.10047. ISSN 1097-0037.
3. Beckenbach, Isabel; Borndörfer, Ralf (2018-10-01). "Hall's and Kőnig's theorem in graphs and hypergraphs". Discrete Mathematics. 341 (10): 2753–2761. doi:10.1016/j.disc.2018.06.013. ISSN 0012-365X.
4. Füredi, Zoltán (1981-06-01). "Maximum degree and fractional matchings in uniform hypergraphs". Combinatorica. 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.
5. "co.combinatorics - Fractional Matching version of Hall's Marriage theorem". MathOverflow. Retrieved 2020-06-29.
6. Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.

See also

• Fractional coloring