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 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 e1 and e2 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 ν(H). 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.
Intersecting hypergraph A hypergraph H = (V, E) is called intersecting if every two hyperedges in E have a vertex in common. A hypergraph H is intersecting if and only if it has no matching with two or more hyperedges, if and only if ν(H) = 1.
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 ν*(H).
Since a matching is a special case of a fractional matching, for every hypergraph H: Matching-number(H) ≤ fractional-matching-number(H) Symbolically, this principle is written:
ν ( H ) ≤ ν ∗ ( H ) {\displaystyle \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 provides upper bounds on the fractional-matching-number(H) / matching-number(H) ratio:
If each hyperedge in H contains at most r vertices, then
ν ∗ ( H ) ν ( H ) ≤ r − 1 + 1 r . {\displaystyle {\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.}
In particular, in a simple graph:
ν ∗ ( H ) ν ( H ) ≤ 3 2 . {\displaystyle {\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.}
The inequality is sharp: Let Hr be the r-uniform finite projective plane. Then ν(Hr) = 1 since every two hyperedges intersect, and ν*(Hr) = r – 1 + 1/r 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 r2 – r + 1 hyperedges). Therefore the ratio is exactly r – 1 + 1/r. If r is such that the r-uniform finite projective plane does not exist (for example, r = 7), then a stronger inequality holds:
ν ∗ ( H ) ν ( H ) ≤ r − 1. {\displaystyle {\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.}
If H is r-partite (the vertices are partitioned into r parts and each hyperedge contains a vertex from each part), then:
ν ∗ ( H ) ν ( H ) ≤ r − 1. {\displaystyle {\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.}
In particular, in a bipartite graph, ν*(H) = ν(H). This was proved by András Gyárfás.
The inequality is sharp: Let Hr- be the truncated projective plane of order r – 1. Then ν(Hr-) = 1 since every two hyperedges intersect, and ν*(Hr-) = r – 1 by the fractional matching that assigns a weight of 1/r to each hyperedge (there are r2 – r hyperedges).
… excerpt ends here. Continue reading the full article.
