In a simple graphG =, the degree of a vertexv, often denoted by deg or δ, is the number of edges in E adjacent to v. The minimum degree of a graph, often denoted by deg or δ, is the minimum of deg over all vertices v in V. A matching in a graph is a set of edges such that each vertex is adjacent to at most one edge; a perfect matching is a matching in which each vertex is adjacent to exactly one edge. A perfect matching does not always exist, and thus it is interesting to find sufficient conditions that guarantee its existence. One such condition follows fromDirac's theorem on Hamiltonian cycles. It says that, if deg ≥ n/2, then the graph admits a Hamiltonian cycle; this implies that it admits a perfect matching. The factor n/2 is tight, since the complete bipartite graph on vertices has degree n/2-1 but does not admit a perfect matching. The results described below aim to extend these results from graphs to hypergraphs.
Degrees in hypergraphs
In a hypergraph H =, each edge of E may contain more than two vertices of V. The degree of a vertex v in V is, as before, the number of edges in E that contain v. But in a hypergraph we can also consider the degree of subsets of vertices: given a subset U of V, deg is the number of edges in E that contain all vertices of U. Thus, the degree of a hypergraph can be defined in different ways depending on the size of subsets whose degree is considered. Formally, for every integer d ≥ 1, degd is the minimum of deg over all subsets U of V that contain exactly d vertices. Thus, deg1 corresponds to the definition of a degree of a simple graph, namely the smallest degree of a single vertex; deg2 is the smallest degree of a pair of vertices; etc. A hypergraph H = is called r-uniform if every hyperedge in E contains exactly r vertices of V. In r-uniform graphs, the relevant values of d are 1, 2,..., r-1. In a simple graph, r=2.
Conditions on 1-vertex degree
Several authors proved sufficient conditions for the case d=1, i.e., conditions on the smallest degree of a single vertex.
If H is a 3-uniform hypergraph on n vertices, n is a multiple of 3, and, then H contains a perfect matching.
If H is a 3-uniform hypergraph on n vertices, n is a multiple of 3, and, then H contains a perfect matching - a matching of size k. This result is the best possible.
If H is a 4-uniform hypergraph with on n vertices, n is a multiple of 4, and, then H contains a perfect matching - matching of size k. This result is the best possible.
If H is r-uniform, n is a multiple of r, and, then H contains a matching of size at least k+1. In particular, setting k=n/r-1 gives that, if, then H contains a perfect matching.
If H is r-uniform and r-partite, each side contains exactly n vertices, and, then H contains a matching of size at least k+1. In particular, setting k=n-1 gives that if, then H contains a perfect matching.
For comparison, Dirac's theorem on Hamiltonian cycles says that, if H is 2-uniform and , then H admits a perfect matching.
Conditions on (r-1)-tuple degree
Several authors proved sufficient conditions for the case d=r-1, i.e., conditions on the smallest degree of sets of r-1 vertices, in r-uniform hypergraphs with n vertices.
In ''r''-partite ''r''-uniform hypergraphs
The following results relate to r-partite hypergraphs that have exactly n vertices on each side :
If n≥1000 and, then H has a perfect matching. This expression is smallest possible up to the lower-order term; in particular, n/2 is not sufficient.
If , then H admits a matching that covers all but at most r-2 vertices in each vertex class of H. The n/r factor is essentially the best possible.
Let V1,...,Vr be the r sides of H. If the degree of every -tuple in V\V1 is strictly larger than n/2, and the degree of every -tuple in V\Vr is at least n/2, then H admits a perfect matching.
In general ''r''-uniform hypergraphs
For every γ>0, when n is large enough, if then H is Hamiltonian, and thus contains a perfect matching.
When n is not divisible by r, the sufficient degree is close to n/r: if ' then H admits a perfect matching. The expression is almost the smallest possible: the smallest possible is '.
Other conditions
There are some sufficient conditions for other values of d:
For all d ≥ r / 2, the threshold for degd is close to.
For all d < r / 2, the threshold for degd is at most .
If H is r-partite and each side contains exactly n vertices, and, then H contains a matching covering all but r vertices.
If n is sufficiently large and divisible by r, and, then H contains a matching covering all but r vertices.
