Matching in hypergraphs
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).
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.
[4] 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.
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.
A theorem by Zoltán Füredi[4] provides upper bounds on the fractional-matching-number(H) / matching-number(H) ratio:
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.
Consider a hypergraph H in which each hyperedge contains at most n vertices.
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.
There are various sufficient conditions for the existence of a perfect matching in a hypergraph: 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.
The problem of finding a maximum-cardinality matching in a hypergraph, thus calculating
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.
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).
The vertex-cover number of a hypergraph H is the smallest size of a vertex cover in H. It is often denoted by τ(H),[1]: 466 for transversal.
Linear programming duality implies that, for every hypergraph H: fractional-matching-number (H) = fractional-vertex-cover-number(H).
The Kőnig-Egerváry theorem shows that every bipartite graph has the Kőnig property.
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.
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 (v1, e1, v2, e2, …, vk, ek, vk+1 = v1), where the vi are distinct vertices and the ei are distinct hyperedges, and each hyperedge contains the vertex to its left and the vertex to its right.
Claude Berge proved that a hypergraph is balanced if and only if it does not contain an unbalanced odd-length circuit.
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.