Matching in hypergraphs

The red set of edges is a perfect matching, because it contains every vertex of the hypergraph. The yellow set is a maximum-cardinality matching, because it contains the most amount of edges possible for a matching in this hypergraph, and the matching number is therefore 3.

In a regular graph, if one has a perfect matching, that same matching is definitionally the maximum-cardinality matching for the graph, but in a hypergraph, where the number of vertices connected by an edge is variable, they can be 2 distinct matchings, as shown here.

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.Template:Rp

Definition

Recall that a hypergraph Template:Mvar is a pair Template:Math, where Template:Mvar is a set of vertices and Template:Mvar is a set of subsets of Template:Mvar called hyperedges. Each hyperedge may contain one or more vertices.

A matching in Template:Mvar is a subset Template:Mvar of Template:Mvar, such that every two hyperedges Template:Math and Template:Math in Template:Mvar have an empty intersection (have no vertex in common).

The matching number of a hypergraph Template:Mvar is the largest size of a matching in Template:Mvar. It is often denoted by Template:Math.Template:Rp

As an example, let Template:Mvar be the set Template:Math Consider a 3-uniform hypergraph on Template:Mvar (a hypergraph in which each hyperedge contains exactly 3 vertices). Let Template:Mvar be a 3-uniform hypergraph with 4 hyperedges:

Template:Math

Then Template:Mvar admits several matchings of size 2, for example:

Template:Math

Template:Math

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 Template:Mvar is 2.

Intersecting hypergraphTemplate:Anchor

A hypergraph Template:Math is called intersecting if every two hyperedges in Template:Mvar have a vertex in common. A hypergraph Template:Mvar is intersecting if and only if it has no matching with two or more hyperedges, if and only if Template:Math.

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 Template:Math and 3 edges:

Template:Math

By the above definition, a matching in a graph is a set Template:Mvar of edges, such that each two edges in Template:Mvar have an empty intersection. This is equivalent to saying that no two edges in Template:Mvar 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 Template:Math to each hyperedge, such that for every vertex Template:Mvar in Template:Mvar, the sum of fractions of hyperedges containing Template:Mvar 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 Template:Mvar is the largest size of a fractional matching in Template:Mvar. It is often denoted by Template:Math.

Since a matching is a special case of a fractional matching, for every hypergraph Template:Mvar:

Matching-number(Template:Mvar) ≤ fractional-matching-number(Template:Mvar)

Symbolically, this principle is written:

$\nu (H)\le {\nu }^{*}(H)$

In general, the fractional matching number may be larger than the matching number. A theorem by Zoltán Füredi provides upper bounds on the fractional-matching-Template:Nowrapnumber(Template:Mvar) ratio:

• If each hyperedge in Template:Mvar contains at most Template:Mvar vertices, then

$\frac{{\nu }^{*}(H)}{\nu (H)}\le r-1+\frac{1}{r}.$

In particular, in a simple graph:

$\frac{{\nu }^{*}(H)}{\nu (H)}\le \frac{3}{2}.$

• • The inequality is sharp: Let Template:Mvar be the Template:Mvar-uniform finite projective plane. Then Template:Math since every two hyperedges intersect, and Template:Math by the fractional matching that assigns a weight of Template:Math to each hyperedge (it is a matching since each vertex is contained in Template:Mvar hyperedges, and its size is Template:Math since there are Template:Math hyperedges). Therefore the ratio is exactly Template:Math.
• If Template:Mvar is such that the Template:Mvar-uniform finite projective plane does not exist (for example, Template:Math), then a stronger inequality holds:

$\frac{{\nu }^{*}(H)}{\nu (H)}\le r-1.$

• If Template:Mvar is Template:Mvar-partite (the vertices are partitioned into Template:Mvar parts and each hyperedge contains a vertex from each part), then:

$\frac{{\nu }^{*}(H)}{\nu (H)}\le r-1.$

In particular, in a bipartite graph, Template:Math. This was proved by András Gyárfás.

• • The inequality is sharp: Let Template:Mvar be the truncated projective plane of order Template:Math. Then Template:Math since every two hyperedges intersect, and Template:Math by the fractional matching that assigns a weight of Template:Math to each hyperedge (there are Template:Math hyperedges).

Perfect matching

A matching Template:Mvar is called perfect if every vertex Template:Mvar in Template:Mvar is contained in exactly one hyperedge of Template:Mvar. This is the natural extension of the notion of perfect matching in a graph.

A fractional matching Template:Mvar is called perfect if for every vertex Template:Mvar in Template:Mvar, the sum of fractions of hyperedges in Template:Mvar containing Template:Mvar is exactly 1.

Consider a hypergraph Template:Mvar in which each hyperedge contains at most Template:Mvar vertices. If Template:Mvar admits a perfect fractional matching, then its fractional matching number is at least Template:Math. If each hyperedge in Template:Mvar contains exactly Template:Mvar vertices, then its fractional matching number is at exactly Template:Math. Template:Rp This is a generalization of the fact that, in a graph, the size of a perfect matching is Template:Math.

Given a set Template:Mvar of vertices, a collection Template:Mvar of subsets of Template:Mvar is called balanced if the hypergraph Template:Math admits a perfect fractional matching.

For example, if Template:Math and Template:Math then Template:Mvar is balanced, with the perfect fractional matching Template:Math

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.

Balanced set-family

A set-family Template:Mvar over a ground set Template:Mvar is called balanced (with respect to Template:Mvar) if the hypergraph Template:Math admits a perfect fractional matching. Template:Rp

For example, consider the vertex set Template:Math and the edge set Template:Math Template:Mvar is balanced, since there is a perfect fractional matching with weights Template:Math

Computing a maximum matching

The problem of finding a maximum-cardinality matching in a hypergraph, thus calculating $\nu (H)$, 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 Template:Math is a subset Template:Mvar of Template:Mvar, such that every hyperedge in Template:Mvar contains at least one vertex of Template:Mvar (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 Template:Mvar is the smallest size of a vertex cover in Template:Mvar. It is often denoted by Template:Math,Template:Rp for transversal.

A fractional vertex-cover is a function assigning a weight to each vertex in Template:Mvar, such that for every hyperedge Template:Mvar in Template:Mvar, the sum of fractions of vertices in Template:Mvar 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 Template:Mvar is the smallest size of a fractional vertex-cover in Template:Mvar. It is often denoted by Template:Math.

Since a vertex-cover is a special case of a fractional vertex-cover, for every hypergraph Template:Mvar:

fractional-vertex-cover-number (Template:Mvar) ≤ vertex-cover-number (Template:Mvar).

Linear programming duality implies that, for every hypergraph Template:Mvar:

fractional-matching-number (Template:Mvar) = fractional-vertex-cover-number(Template:Mvar).

Hence, for every hypergraph Template:Mvar:

$\nu (H)\le {\nu }^{*}(H)={\tau }^{*}(H)\le \tau (H)$

If the size of each hyperedge in Template:Mvar is at most Template:Mvar 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:

$\tau (H)\le r\cdot \nu (H).$

This inequality is tight: equality holds, for example, when Template:Mvar contains Template:Math vertices and Template:Mvar contains all subsets of Template:Mvar vertices.

However, in general Template:Math, since Template:Math; see Fractional matching above.

Ryser's conjecture says that, in every Template:Mvar-partite Template:Mvar-uniform hypergraph:

$\tau (H)\le (r-1)\nu (H).$

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 Template:Math. 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.Template:Rp

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 Template:Math with all triplets Template:Math It is 2-colorable, for example, we can color Template:Math blue and Template:Math white. However, its matching number is 1 and its vertex-cover number is 2.

A stronger generalization is as follows. Given a hypergraph Template:Math and a subset Template:Mvar of Template:Mvar, the restriction of Template:Mvar to Template:Mvar is the hypergraph whose vertices are Template:Mvar, and for every hyperedge Template:Mvar in Template:Mvar that intersects Template:Mvar, it has a hyperedge Template:Mvar that is the intersection of Template:Mvar and Template:Mvar. A hypergraph is called balanced if all its restrictions are essentially 2-colorable, meaning that we ignore singleton hyperedges in the restriction. 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 Template:Mvar in a hypergraph is an alternating sequence Template:Math, where the Template:Mvar are distinct vertices and the Template:Mvar are distinct hyperedges, and each hyperedge contains the vertex to its left and the vertex to its right. The circuit is called unbalanced if each hyperedge contains no other vertices in the circuit. Claude Berge proved that a hypergraph is balanced if and only if it does not contain an unbalanced odd-length circuit. Every balanced hypergraph has Kőnig's property.Template:Rp

The following are equivalent:Template:Rp

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

Matching and packing

The problem of set packing is equivalent to hypergraph matching.

A vertex-packing in a (simple) graph is a subset Template:Mvar of its vertices, such that no two vertices in Template:Mvar 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:Template:Rp

• Given a hypergraph Template:Math, define its intersection graph Template:Math as the simple graph whose vertices are Template:Mvar and whose edges are pairs Template:Math such that Template:Math, Template:Math have a vertex in common. Then every matching in Template:Mvar is a vertex-packing in Template:Math and vice versa.
• Given a graph Template:Math, define its star hypergraph Template:Math as the hypergraph whose vertices are Template:Mvar and whose hyperedges are the stars of the vertices of Template:Mvar (i.e., for each vertex Template:Mvar in Template:Mvar, there is a hyperedge in Template:Math that contains all edges in Template:Mvar that are adjacent to Template:Mvar). Then every vertex-packing in Template:Mvar is a matching in Template:Math and vice versa.
• Alternatively, given a graph Template:Math, define its clique hypergraph Template:Math as the hypergraph whose vertices are the cliques of Template:Mvar, and for each vertex Template:Mvar in Template:Mvar, there is a hyperedge in Template:Math containing all cliques in Template:Mvar that contain Template:Mvar. Then again, every vertex-packing in Template:Mvar is a matching in Template:Math and vice versa. Note that Template:Math cannot be constructed from Template:Mvar 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.
• Erdős–Ko–Rado theorem on pairwise non-disjoint edges in hypergraphs