Perfect matching in high-degree hypergraphs

Template:Short description 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 Template:Math, the degree of a vertex Template:Mvar, often denoted by Template:Math or Template:Math, is the number of edges in Template:Mvar adjacent to Template:Mvar. The minimum degree of a graph, often denoted by Template:Math or Template:Math, is the minimum of Template:Math over all vertices Template:Mvar in Template:Mvar.

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 Template:Math, then the graph admits a Hamiltonian cycle; this implies that it admits a perfect matching. The factor Template:Math is tight, since the complete bipartite graph on Template:Math vertices has degree Template:Math 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 Template:Math, each edge of Template:Mvar may contain more than two vertices of Template:Mvar. The degree of a vertex Template:Mvar in Template:Mvar is, as before, the number of edges in Template:Mvar that contain Template:Mvar. But in a hypergraph we can also consider the degree of subsets of vertices: given a subset Template:Mvar of Template:Mvar, Template:Math is the number of edges in Template:Mvar that contain all vertices of Template:Mvar. 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 Template:Math, Template:Math is the minimum of Template:Math over all subsets Template:Mvar of Template:Mvar that contain exactly Template:Mvar vertices. Thus, Template:Math corresponds to the definition of a degree of a simple graph, namely the smallest degree of a single vertex; Template:Math is the smallest degree of a pair of vertices; etc.

A hypergraph Template:Math is called Template:Mvar-uniform if every hyperedge in Template:Mvar contains exactly Template:Mvar vertices of Template:Mvar. In Template:Mvar-uniform graphs, the relevant values of Template:Mvar are Template:Math. In a simple graph, Template:Math.

Conditions on 1-vertex degree

Several authors proved sufficient conditions for the case Template:Math, i.e., conditions on the smallest degree of a single vertex.

• If Template:Mvar is a 3-uniform hypergraph on Template:Mvar vertices, Template:Mvar is a multiple of 3, and

  ${\mathrm{deg}}_1(H)\ge (5/9+o(1))(\genfrac{}{}{0ex}{}{n}{2}),$

  then Template:Mvar contains a perfect matching.

• If Template:Mvar is a 3-uniform hypergraph on Template:Mvar vertices, Template:Mvar is a multiple of 3, and

  ${\mathrm{deg}}_1(H)\ge (\genfrac{}{}{0ex}{}{n-1}{2})-(\genfrac{}{}{0ex}{}{2n/3}{2})+1,$

  then Template:Mvar contains a perfect matching - a matching of size Template:Mvar. This result is the best possible.

• If Template:Mvar is a 4-uniform hypergraph with on Template:Mvar vertices, Template:Mvar is a multiple of 4, and

  ${\mathrm{deg}}_1(H)\ge (\genfrac{}{}{0ex}{}{n-1}{3})-(\genfrac{}{}{0ex}{}{3n/4}{3}),$

  then Template:Mvar contains a perfect matching - a matching of size Template:Mvar. This result is the best possible.

• If Template:Mvar is Template:Mvar-uniform, n is a multiple of Template:Mvar, and

  ${\mathrm{deg}}_1(H)>\frac{r-1}{r}\left((\genfrac{}{}{0ex}{}{n-1}{r-1})-(\genfrac{}{}{0ex}{}{n-kr-1}{r-1})\right),$

  then Template:Mvar contains a matching of size at least Template:Math. In particular, setting Template:Math gives that, if

  ${\mathrm{deg}}_1(H)>\frac{r-1}{r}\left((\genfrac{}{}{0ex}{}{n-1}{r-1})-1\right),$

  then Template:Mvar contains a perfect matching.

• If Template:Mvar is Template:Mvar-uniform and Template:Mvar-partite, each side contains exactly Template:Mvar vertices, and

  ${\mathrm{deg}}_1(H)>\frac{r-1}{r}\left(n^{r-1}-(n-k{)}^{r-1}\right),$

  then Template:Mvar contains a matching of size at least Template:Math. In particular, setting Template:Math gives that if

  ${\mathrm{deg}}_1(H)>\frac{r-1}{r}\left(n^{r-1}-1\right),$

  then Template:Mvar contains a perfect matching.

For comparison, Dirac's theorem on Hamiltonian cycles says that, if Template:Mvar is 2-uniform (i.e., a simple graph) and

${\mathrm{deg}}_1(H)\ge (\genfrac{}{}{0ex}{}{n-1}{1})-(\genfrac{}{}{0ex}{}{n/2}{1})+1=n/2,$

then Template:Mvar admits a perfect matching.

Conditions on (r-1)-tuple degree

Several authors proved sufficient conditions for the case Template:Math, i.e., conditions on the smallest degree of sets of Template:Math vertices, in Template:Mvar-uniform hypergraphs with Template:Mvar vertices.

In r-partite r-uniform hypergraphs

The following results relate to Template:Mvar-partite hypergraphs that have exactly Template:Mvar vertices on each side (Template:Mvar vertices overall):

• If ${\mathrm{deg}}_{r-1}(H)\ge n/2+\sqrt{2n{\log }_{2}n}$

  and Template:Math, then Template:Mvar has a perfect matching. This expression is smallest possible up to the lower-order term; in particular, Template:Math is not sufficient.

• If ${\mathrm{deg}}_{r-1}(H)\ge n/r$

  then Template:Mvar admits a matching that covers all but at most Template:Math vertices in each vertex class of Template:Mvar. The Template:Math factor is essentially the best possible.

• Let Template:Math be the Template:Mvar sides of Template:Mvar. If the degree of every Template:Math-tuple in Template:Math is strictly larger than Template:Math, and the degree of every Template:Math-tuple in Template:Math is at least Template:Math, then Template:Mvar admits a perfect matching.

In general r-uniform hypergraphs

• For every Template:Math, when Template:Mvar is large enough, if

  ${\mathrm{deg}}_{r-1}(H)\ge (1/2+\gamma )n$

  then Template:Mvar is Hamiltonian, and thus contains a perfect matching.

• If ${\mathrm{deg}}_{r-1}(H)\ge n/2+3r^2\sqrt{n{\log }_{2}n}$

  and Template:Mvar is sufficiently large, then Template:Mvar admits a perfect matching.

• If ${\mathrm{deg}}_{r-1}(H)\ge n/r+3r^2\sqrt{n{\log }_{2}n},$

  then Template:Mvar admits a matching that covers all but at most Template:Math vertices.

• When Template:Mvar is divisible by Template:Mvar and sufficiently large, the threshold is

  ${\mathrm{deg}}_{r-1}(H)\ge n/2-r+c_{k,n}$

  where Template:Math is a constant depending on the parity of Template:Mvar and Template:Mvar (all expressions below are the best possible):

  • 3 when Template:Math is even and Template:Math is odd;
  • Template:Frac when Template:Mvar is odd and Template:Math is odd;
  • Template:Frac when Template:Mvar is odd and Template:Math is even;
  • 2 otherwise.
• When Template:Mvar is not divisible by Template:Mvar, the sufficient degree is close to Template:Math: if Template:Math, then Template:Mvar admits a perfect matching. The expression is almost the smallest possible: the smallest possible is Template:Math.

Other conditions

There are some sufficient conditions for other values of Template:Mvar:

• For all Template:Math, the threshold for Template:Math is close to:

  $(\frac{1}{2}+o(1))(\genfrac{}{}{0ex}{}{n}{r-d}).$

• For all Template:Math, the threshold for Template:Math is at most:

  $(\frac{r-d}{r}+o(1))(\genfrac{}{}{0ex}{}{n-d}{r-d})$

• If Template:Mvar is Template:Mvar-partite and each side contains exactly Template:Mvar vertices, and

  ${\mathrm{deg}}_d(H)\ge \frac{r-d}{r}{n}^{r-d}+r{n}^{r-d-1},$

  then Template:Mvar contains a matching covering all but Template:Math vertices.

• If Template:Mvar is sufficiently large and divisible by Template:Mvar, and

  ${\mathrm{deg}}_d(H)\ge \frac{r-d}{r}(\genfrac{}{}{0ex}{}{n}{r-d})+r^{r+1}(\ln n{)}^{1/2}{n}^{r-d-1/2},$

  then Template:Mvar contains a matching covering all but Template:Math vertices.

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.