Perfect matching in high-degree hypergraphs

In graph theory, perfect matching in high-degree hypergraphs is a research avenue trying to find sufficient conditions for existence of a perfect matching in a hypergraph, based only on the degree of vertices or subsets of them.

Introduction

Degrees and matchings in graphs

In a simple graph G = (V, E), the degree of a vertex v, often denoted by deg(v) or δ(v), is the number of edges in E adjacent to v. The minimum degree of a graph, often denoted by deg(G) or δ(v), is the minimum of deg(v) 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 from Dirac's theorem on Hamiltonian cycles. It says that, if deg(G) ≥ 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 (n/2-1, n/2+1) 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 = (V, E), 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(U) 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, deg_d(H) is the minimum of deg(U) over all subsets U of V that contain exactly d vertices. Thus, deg₁(H) corresponds to the definition of a degree of a simple graph, namely the smallest degree of a single vertex; deg₂(H) is the smallest degree of a pair of vertices; etc.

A hypergraph H = (V, E) 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 the minimum vertex degree

Khan proved two 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=3 k vertices, and $\deg _{1}(H)\geq {n-1 \choose 2}-{2n/3 \choose 2}+1$, 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 = 4 k vertices, and $\deg _{1}(H)\geq {n-1 \choose 3}-{3n/4 \choose 3}$, then H contains a perfect matching - matching of size k. This result is the best possible.

For comparison, Dirac's theorem on Hamiltonian cycles says that, if H is 2-uniform (i.e., a simple graph) and $\deg _{1}(H)\geq {n-1 \choose 1}-{n/2 \choose 1}+1=n/2$, then H admits a perfect matching.

Conditions on the minimum collective 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.

• For every γ>0, when n is large enough, if $\deg _{r-1}(H)\geq (1/2+\gamma )n$ then H is Hamiltonian, and thus contains a perfect matching.
• If n is sufficiently large and $\deg _{r-1}(H)\geq n/2+3r^{2}{\sqrt {n\log _{2}n}}$, then H admits a perfect matching. If $\deg _{r-1}(H)\geq n/r+3r^{2}{\sqrt {n\log _{2}n}}$, then H admits a matching that covers all but at most 2r² vertices.
• If H is r-partite and n≥1000 and $\deg _{r-1}(H)\geq n/2+{\sqrt {2n\log _{2}n}}$, then H admits a perfect matching. If H is r-partite and $\deg _{r-1}(H)\geq n/r$, then H admits a matching that covers all but at most r-2 vertices in each vertex class of H. These factors are the best possible up to the error term.

• When n is divisible by r and sufficiently large, the sufficient degree is close to n/2 (all expressions below are the best possible):
  • When r/2 is even and n/r is odd, the threshold is $\deg _{r-1}(H)\geq n/2-r+3$;
  • When r is odd and (n-1)/2 is odd, the threshold is $\deg _{r-1}(H)\geq n/2-r+5/2$;
  • When r is odd and (n-1)/2 is even, the threshold is $\deg _{r-1}(H)\geq n/2-r+3/2$;
  • Otherwise, the threshold is $\deg _{r-1}(H)\geq n/2-r+2$.
• When n is not divisible by r, the sufficient degree is close to n/r: if $\deg _{r-1}(H)\geq n/r+O(\log(n))$ then H admits a perfect matching. The expression is almost the smallest possible: the smallest possible is $\lfloor n/r\rfloor$.

See also

• Hall-type theorems for hypergraphs - lists other sufficient conditions for the existence of perfect matchings in hypergraphs, analogous to Hall's marriage theorem.