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.
Definition
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 .
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.
Intersecting hypergraph
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 .
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 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.
Fractional matching
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-number() Symbolically, this principle is written:
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-number() ratio:
If each hyperedge in contains at most vertices, then In particular, in a simple graph: The inequality is sharp: Let be the -uniform finite projective plane. Then since every two hyperedges intersect, and by the fractional matching that assigns a weight of to each hyperedge (it is a matching since each vertex is contained in hyperedges, and its size is since there are hyperedges). Therefore the ratio is exactly . If is such that the -uniform finite projective plane does not exist (for example, ), then a stronger inequality holds: If is -partite (the vertices are partitioned into 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. The inequality is sharp: Let be the truncated projective plane of order . Then since every two hyperedges intersect, and by the fractional matching that assigns a weight of to each hyperedge (there are hyperedges).
Perfect matching
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 . 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: