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

In a simple graph G = (V, E), the degree of a vertex v, often denoted by deg(v), is the number of edges in E adjacent to v. The minimum degree of a graph, often denoted by deg(G), 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.

Khan's conditions: smallest vertex degree

Given a hypergraph H = (V,E), the degree of a vertex v in V is the number of hyperedges containing v.

Let H = (V, E) be a 3-uniform hypergraph with on n=3 k vertices, such that every the degree of each vertex is at least ${n-1 \choose 2}-{2n/3 \choose 2}+1$. Then H contains a perfect matching - matching of size k. This result is the best possible.

Let H = (V, E) be a 4-uniform hypergraph with on n = 4 k vertices, such that the degree of each vertex is at least ${n-1 \choose 3}-{3n/4 \choose 3}$. Then H contains a perfect matching - matching of size k. This result is the best possible.

These results generalize a known result on graphs (which are 2-uniform hypergraphs): if the degree of each vertex in a graph is at least ${n-1 \choose 1}-{n/2 \choose 1}+1=n/2$, then the graph admits a perfect matching. This follows from Dirac's theorem on Hamiltonian cycles, which says that if the degree of each vertex is at least n/2, then the graph admits a Hamiltonian cycle. The 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.

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.