In graph theory, a **matching** in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.^{[1]}^{: 466–470 } ^{[2]}

## Definition

Recall that a hypergraph *H* is a pair (*V*, *E*), where *V* is a set of *vertices* and *E* is a set of subsets of *V* called *hyperedges*. Each hyperedge may contain one or more vertices.

A **matching** in *H* is a subset *M* of *E*, such that every two hyperedges *e*_{1} and *e*_{2} in *M* have an empty intersection (have no vertex in common).

The **matching number** of a hypergraph *H* is the largest size of a matching in *H*. It is often denoted by .^{[1]}^{: 466 } ^{[3]}

As an example, let *V* be the set {1,2,3,4,5,6,7}. consider a 3-uniform hypergraph on *V* (a hypergraph in which each hyperedge contains exactly 3 vertices). Let *H* be a 3-uniform hypergraph with 4 hyperedges:

- { {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

Then *H* admits several matchings of size 2, for example:

- { {1,2,3}, {4,5,6} }
- { {1,4,5}, {2,3,6} }

However, in any subset of 3 hyperedges, at least two of them intersect, so there is no matching of size 3. Hence, the matching number of *H* is 2.

## Matching in a graph as a special case

A graph without self-loops is just a 2-uniform hypergraph: each edge can be considered as a set of the two vertices that it connects. For example, this 2-uniform hypergraph represents a graph with 4 vertices {1,2,3,4} and 3 edges:

- { {1,3}, {1,4}, {2,4} }

By the above definition, a matching in a graph is a set *M* of edges, such that each two edges in *M* have an empty intersection. This is equivalent to saying that no two edges in M are adjacent to the same vertex; this is exactly the definition of a matching in a graph.

## Fractional matching

A **fractional matching** in a hypergraph is a function that assigns a fraction in [0,1] to each hyperedge, such that for every vertex *v* in *V*, the sum of fractions of hyperedges containing *v* is at most 1. A matching is a special case of a fractional matching in which all fractions are either 0 or 1. The *size* of a fractional matching is the sum of fractions of all hyperedges.

The **fractional matching number** of a hypergraph *H* is the largest size of a fractional matching in *H*. It is often denoted by .^{[3]}

Since a matching is a special case of a fractional matching, for every hypergraph *H*:

matching-number (

H) ≤ fractional-matching-number (H);

In symbols:

In general, the fractional matching number may be larger than the matching number. A theorem of Zoltán Füredi^{[4]} provides upper bounds on the ratio fractional-matching-number(*H*) / matching-number(*H*):

- If each hyperedge in
*H*contains at most*r*vertices, then . In particular, in a simple graph, .^{[5]}- The inequality is sharp: Let
*H*be the_{r}*r*-uniform finite projective plane. Then since every two hyperedges intersect, and by the fractional matching that assigns a weight of 1/*r*to each hyperedge (it is a matching since each vertex is contained in*r*hyperedges, and its size is*r*-1+1/*r*since there are*r*^{2}-*r*+1 hyperedges). Therefore the ratio is exactly*r*-1+1/*r*.

- The inequality is sharp: Let
- If
*r*is such that the*r*-uniform finite projective plane does not exist (for example,*r*=7), then a stronger inequality holds: . - If
*H*is*r*-partite (- the vertices are partitioned into*r*parts and each hyperedge contains a vertex from each part), then In particular, in a bipartite graph, . This was proved by András Gyárfás.^{[4]}- The inequality is sharp: Let
*H*be the truncated projective plane of order_{r-}*r*-1. Then since every two hyperedges intersect, and by the fractional matching that assigns a weight of 1/*r*to each hyperedge (there are*r*^{2}-*r*hyperedges).

- The inequality is sharp: Let

## Perfect matching

A matching *M* is called **perfect** if every vertex *v* in *V* is contained in *exactly* one hyperedge of *M*. This is the natural extension of the notion of perfect matching in a graph.

A fractional matching *M* is called **perfect** if for every vertex *v* in *V*, the sum of fractions of hyperedges in *M* containing *v* is *exactly* 1.

Consider a hypergraph *H* in which each hyperedge contains at most *n* vertices. If *H* admits a perfect fractional matching, then its fractional matching number is at least |V|/*n*. If each hyperedge in *H* contains exactly *n* vertices, then its fractional matching number is at exactly |V|/*n*.^{[6]} ^{: sec.2 } This is a generalization of the fact that, in a graph, the size of a perfect matching is |V|/2.

Given a set *V* of vertices, a collection *E* of subsets of *V* is called *balanced* if the hypergraph (*V*,*E*) admits a perfect fractional matching.

For example, if *V* = {1,2,3,a,b,c} and *E* = { {1,a}, {2,a}, {1,b}, {2,b}, {3,c} }, then *E* is balanced, with the perfect fractional matching { 1/2, 1/2, 1/2, 1/2, 1 }.

There are various sufficient conditions for the existence of a perfect matching in a hypergraph:

- Hall-type theorems for hypergraphs - presents sufficient conditions analogous to Hall's marriage theorem, based on sets of neighbors.
- Perfect matching in high-degree hypergraphs - presents sufficient conditions analogous to Dirac's theorem on Hamiltonian cycles, based on degree of vertices.
- Keevash and Mycroft developed a geometric theory for hypergraph matching.
^{[7]}

## Intersecting hypergraph

A hypergraph *H* = (*V*, *E*) is called *intersecting* if every two hyperedges in *E* have a vertex in common. In an intersecting graph, there is no matching with two or more hyperedges, therefore .^{[4]}

## Balanced set-family

A set-family *E* over a ground set *V* is called *balanced* (with respect to *V*) if the hypergraph *H = (V, E)* admits a perfect fractional matching.^{[6]} ^{: sec.2 }

For example, consider the vertex set *V* = {1,2,3,a,b,c} and the edge set *E* = {1-a, 2-a, 1-b, 2-b, 3-c}. *E* is balanced, since there is a perfect fractional matching with weights {1/2, 1/2, 1/2, 1/2, 1}.

## Computing a maximum matching

The problem of finding a maximum-cardinality matching in a hypergraph, thus calculating , is NP-hard even for 3-uniform hypergraphs (see 3-dimensional matching). This is in contrast to the case of simple (2-uniform) graphs in which computing a maximum-cardinality matching can be done in polynomial time.

## Matching and covering

A **vertex-cover in a hypergraph** *H* = (*V*, *E*) is a subset *T* of *V*, such that every hyperedge in *E* contains at least one vertex of *T* (it is also called a **transversal** or a **hitting set**, and is equivalent to a set cover). It is a generalization of the notion of a vertex cover in a graph.

The **vertex-cover number** of a hypergraph *H* is the smallest size of a vertex cover in *H*. It is often denoted by ,^{[1]}^{: 466 } for transversal.

A **fractional vertex-cover** is a function assigning a weight to each vertex in *V*, such that for every hyperedge *e* in *E*, the sum of fractions of vertices in *e* is at least 1. A vertex cover is a special case of a fractional vertex cover in which all weights are either 0 or 1. The *size* of a fractional vertex-cover is the sum of fractions of all vertices.

The **fractional vertex-cover number** of a hypergraph *H* is the smallest size of a fractional vertex-cover in *H*. It is often denoted by .

Since a vertex-cover is a special case of a fractional vertex-cover, for every hypergraph *H*:

fractional-vertex-cover-number(

H) ≤ vertex-cover-number (H).

Linear programming duality implies that, for every hypergraph *H*:

fractional-matching-number (

H) = fractional-vertex-cover-number(H).

Hence, for every hypergraph *H*:^{[4]}

If the size of each hyperedge in *H* is at most *r* then the union of all hyperedges in a maximum matching is a vertex-cover (if there was an uncovered hyperedge, we could have added it to the matching). Therefore:

.

This inequality is tight: equality holds, for example, when *V* contains vertices and *E* contains all subsets of *r* vertices.

However, in general , since ; see Fractional matching above.

**Ryser's conjecture** says that, in every *r*-partite *r*-uniform hypergraph:

.

Some special cases of the conjecture have been proved; see Ryser's conjecture.

## Kőnig's property

A hypergraph has the **Kőnig property** if its maximum matching number equals its minimum vertex-cover number, namely if . The Kőnig-Egerváry theorem shows that every bipartite graph has the Kőnig property. To extend this theorem to hypergraphs, we need to extend the notion of bipartiteness to hypergraphs.^{[1]}^{: 468 }

A natural generalization is as follows. A hypergraph is called **2-colorable** if its vertices can be 2-colored so that every hyperedge (of size at least 2) contains at least one vertex of each color. An alternative term is Property B. A simple graph is bipartite iff it is 2-colorable. However, there are 2-colorable hypergraphs without Kőnig's property. For example, consider the hypergraph with *V* = {1,2,3,4} with *E* = all triplets = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }. It is 2-colorable, for example, we can color {1,2} blue and {3,4} white. However, its matching number is 1 and its vertex-cover number is 2.

A stronger generalization is as follows. Given a hypergraph *H* = (*V*, *E*) and a subset *V'* of *V*, the **restriction** of *H* to V' is the hypergraph whose vertices are *V*, and for every hyperedge in *e* in *E* that intersects V', it has a hyperedge *e*' that is the intersection of *e* and *V*'. A hypergraph is called **balanced** if all its restrictions are 2-colorable.^{[8]} A simple graph is bipartite iff it is balanced.

A simple graph is bipartite iff it has no odd-length cycles. Similarly, a hypergraph is balanced iff it has no odd-length *circuits*. A circuit of length *k* in a hypergraph is an alternating sequence (*v*_{1}, *e*_{1}, *v*_{2}, *e*_{2}, ..., *v _{k}*,

*e*,

_{k}*v*

_{k}_{+1}=

*v*

_{1}), where the

*v*are distinct vertices and the

_{i}*e*are distinct hyperedges, and each hyperedge contains the vertex to its left and the vertex to its right. The circuit is called

_{i}*unbalanced*if each hyperedge contains no other vertices in the circuit. Claude Berge proved that a hypergraph is balanced iff it does not contain an unbalanced odd-length circuit. Every balanced hypergraph has Kőnig's property.

^{[9]}

^{[1]}

^{: 468–470 }

The following are equivalent:^{[1]}^{: 470–471 }

- Every partial hypergraph of
*H*(i.e., a hypergraph derived from*H*by deleting some hyperedges) has the Kőnig property. - Every partial hypergraph of
*H*has the property that its maximum degree equals its minimum edge coloring number. *H*has the Helly property, and the intersection graph of*H*(the simple graph in which the vertices are*E*and two elements of*E*are linked iff they intersect) is a perfect graph.

## Matching and packing

A **vertex-packing** in a (simple) graph is a subset *P* of its vertices, such that no two vertices in *P* are adjacent.

The problem of finding a maximum vertex-packing in a graph is equivalent to the problem of finding a maximum matching in a hypergraph:^{[1]}^{: 467 }

- Given a hypergraph
*H*= (*V*,*E*), define its*intersection graph*Int(*H*) as the simple graph whose vertices are*E*and whose edges are pairs (*e*_{1},*e*_{2}) such that*e*_{1},*e*_{2}have a vertex in common. Then every matching in*H*is a vertex-packing in Int(*H*) and vice versa. - Given a graph
*G*= (*V*',*E*'), define its*star hypergraph*St(*G*) as the hypergraph whose vertices are*E*' and whose hyperedges are the stars of the vertices of G (i.e., for each vertex*v*' in*V*', there is a hyperedge in St(*G*) that contains all edges in*E*' that are adjacent to*v*'). Then every vertex-packing in G is a matching in St(*G*) and vice versa. - Alternatively, given a graph
*G*= (*V*',*E*'), define its*clique hypergraph*Cl(*G*) as the hypergraph whose vertices are the cliques of*G,*and for each vertex*v*' in*V*', there is a hyperedge in Cl(*G*) containing all cliques in*G*that contain*v*'. Then again, every vertex-packing in*G*is a matching in Cl(*G*) and vice versa. Note that Cl(*G*) cannot be constructed from*G*in polynomial time, so it cannot be used as a reduction for proving NP-hardness. But it has some theoretical uses.

## See also

- 3-dimensional matching – a special case of hypergraph matching to 3-uniform hypergraphs.
- Vertex cover in hypergraphs
- Bipartite hypergraph
- Rainbow matching in hypergraphs
- D-interval hypergraph - an infinite hypergraph in which there is some relation between the matching and the covering number.

## References

- ^
^{a}^{b}^{c}^{d}^{e}^{f}^{g}Lovász, László; Plummer, M. D. (1986),*Matching Theory*, Annals of Discrete Mathematics,**29**, North-Holland, ISBN 0-444-87916-1, MR 0859549 **^**Berge, Claude (1973).*Graphs and Hypergraphs*. Amsterdam: North-Holland.- ^
^{a}^{b}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. - ^
^{a}^{b}^{c}^{d}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. **^**Lovász, L. (1974). Berge, Claude; Ray-Chaudhuri, Dijen (eds.). "Minimax theorems for hypergraphs".*Hypergraph Seminar*. Lecture Notes in Mathematics. Berlin, Heidelberg: Springer.**411**: 111–126. doi:10.1007/BFb0066186. ISBN 978-3-540-37803-7.- ^
^{a}^{b}Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "Fair division with multiple pieces".*Discrete Applied Mathematics*.**283**: 115–122. arXiv:1710.09477. doi:10.1016/j.dam.2019.12.018. ISSN 0166-218X. S2CID 119602376. **^**Keevash, Peter; Mycroft, Richard (2015-01-01).*A geometric theory for hypergraph matching*. Memoirs of the American Mathematical Society.**233**. American Mathematical Society. ISBN 978-1-4704-0965-4.**^**Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (ed.), "CHAPTER 2 – Balanced Hypergraphs and Some Applications to Graph Theory",*A Survey of Combinatorial Theory*, North-Holland, pp. 15–23, ISBN 978-0-7204-2262-7, retrieved 2020-06-19**^**Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes".*Annals of the New York Academy of Sciences*.**175**(1): 32–40. doi:10.1111/j.1749-6632.1970.tb56451.x. ISSN 1749-6632.