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]
Recall that a hypergraph is a pair, where is a set of vertices and is a set of subsets of called hyperedges. Each hyperedge may contain one or more vertices.
A matching in is a subset of, such that every two hyperedges and in have an empty intersection (have no vertex in common).
The matching number of a hypergraph is the largest size of a matching in . It is often denoted by . [2]
As an example, let be the set Consider a 3-uniform hypergraph on (a hypergraph in which each hyperedge contains exactly 3 vertices). Let be a 3-uniform hypergraph with 4 hyperedges:
Then admits several matchings of size 2, for example:
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 is 2.
A hypergraph is called intersecting if every two hyperedges in have a vertex in common. A hypergraph is intersecting if and only if it has no matching with two or more hyperedges, if and only if .
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 and 3 edges:
By the above definition, a matching in a graph is a set of edges, such that each two edges in have an empty intersection. This is equivalent to saying that no two edges in are adjacent to the same vertex; this is exactly the definition of a matching in a graph.
A fractional matching in a hypergraph is a function that assigns a fraction in to each hyperedge, such that for every vertex in, the sum of fractions of hyperedges containing 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 is the largest size of a fractional matching in . It is often denoted by .
Since a matching is a special case of a fractional matching, for every hypergraph :
Matching-number ≤ fractional-matching-numberSymbolically, this principle is written:
\nu(H)\leq\nu*(H)
In general, the fractional matching number may be larger than the matching number. A theorem by Zoltán Füredi[3] provides upper bounds on the fractional-matching-number ratio:
| \nu*(H) | |
| \nu(H) |
\leqr-1+
| 1 | |
| r |
.
In particular, in a simple graph:[4]
| \nu*(H) | |
| \nu(H) |
\leq
| 3 | |
| 2 |
.
| \nu*(H) | |
| \nu(H) |
\leqr-1.
| \nu*(H) | |
| \nu(H) |
\leqr-1.
In particular, in a bipartite graph, . This was proved by András Gyárfás.
A matching is called perfect if every vertex in is contained in exactly one hyperedge of . This is the natural extension of the notion of perfect matching in a graph.
A fractional matching is called perfect if for every vertex in, the sum of fractions of hyperedges in containing is exactly 1.
Consider a hypergraph in which each hyperedge contains at most vertices. If admits a perfect fractional matching, then its fractional matching number is at least . If each hyperedge in contains exactly vertices, then its fractional matching number is at exactly .[5] This is a generalization of the fact that, in a graph, the size of a perfect matching is .
Given a set of vertices, a collection of subsets of is called balanced if the hypergraph admits a perfect fractional matching.
For example, if and then is balanced, with the perfect fractional matching
There are various sufficient conditions for the existence of a perfect matching in a hypergraph:
A set-family over a ground set is called balanced (with respect to) if the hypergraph admits a perfect fractional matching.
For example, consider the vertex set and the edge set is balanced, since there is a perfect fractional matching with weights
The problem of finding a maximum-cardinality matching in a hypergraph, thus calculating
\nu(H)
A vertex-cover in a hypergraph is a subset of, such that every hyperedge in contains at least one vertex of (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 is the smallest size of a vertex cover in . It is often denoted by, for transversal.
A fractional vertex-cover is a function assigning a weight to each vertex in, such that for every hyperedge in, the sum of fractions of vertices in 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 is the smallest size of a fractional vertex-cover in . It is often denoted by .
Since a vertex-cover is a special case of a fractional vertex-cover, for every hypergraph :
fractional-vertex-cover-number ≤ vertex-cover-number .Linear programming duality implies that, for every hypergraph :
fractional-matching-number = fractional-vertex-cover-number.Hence, for every hypergraph :
\nu(H)\leq\nu*(H)=\tau*(H)\leq\tau(H)
\tau(H)\leqr ⋅ \nu(H).
However, in general, since ; see Fractional matching above.
Ryser's conjecture says that, in every -partite -uniform hypergraph:
\tau(H)\leq(r-1)\nu(H).
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.
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 with all triplets It is 2-colorable, for example, we can color blue and white. However, its matching number is 1 and its vertex-cover number is 2.
A stronger generalization is as follows. Given a hypergraph and a subset of, the restriction of to is the hypergraph whose vertices are, and for every hyperedge in that intersects, it has a hyperedge that is the intersection of and . 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 in a hypergraph is an alternating sequence, where the are distinct vertices and the 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.[7]
The following are equivalent:
The problem of set packing is equivalent to hypergraph matching.
A vertex-packing in a (simple) graph is a subset of its vertices, such that no two vertices in 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: