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

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

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

Conditions on 1-vertex degree

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

* If is a 3-uniform hypergraph on vertices, is a multiple of 3, and

$\deg_1(H)\geq\bigg(5/9+o(1)\bigg),$

then contains a perfect matching.

* If is a 3-uniform hypergraph on vertices, is a multiple of 3, and

$\deg_1(H)\geq - +1,$

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

* If is a 4-uniform hypergraph with on vertices, is a multiple of 4, and

$\deg_1(H)\geq - ,$

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

* If is -uniform, n is a multiple of , and

$\deg_1(H)> \frac\left( \right),$

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

$\deg_1(H)> \frac\left( \right),$

then contains a perfect matching.

* If is -uniform and -partite, each side contains exactly vertices, and

$\deg_1(H)> \frac\left( \right),$

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

$\deg_1(H)> \frac\left( \right),$

then contains a perfect matching.

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

Conditions on (r-1)-tuple degree

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

In ''r''-partite ''r''-uniform hypergraphs

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

* If $\deg_(H)\geq n/2 + \sqrt$

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

* If $\deg_(H)\geq n/r$

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

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

In general ''r''-uniform hypergraphs

* For every , when is large enough, if

$\deg_(H) \geq (1/2+\gamma)n$

then is Hamiltonian, and thus contains a perfect matching.

* If $\deg_(H)\geq n/2 + 3 r^2 \sqrt$

and is sufficiently large, then admits a perfect matching.

* If $\deg_(H)\geq n/r + 3 r^2 \sqrt,$

then admits a matching that covers all but at most vertices.

* When is divisible by and sufficiently large, the threshold is

$\deg_(H)\geq n/2 - r + c_$

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

** 3 when is even and is odd;
** when is odd and is odd;
** when is odd and is even;
** 2 otherwise.
* When is not divisible by , the sufficient degree is close to : if , then 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 :

* For all , the threshold for is close to:

$\left(\frac+o(1)\right)\binom.$

* For all , the threshold for is at most:

$\left(\frac+o(1)\right)\binom$

* If is -partite and each side contains exactly vertices, and

$\deg_d(H) \geq \fracn^ + r n^,$

then contains a matching covering all but vertices.

* If is sufficiently large and divisible by , and

$\deg_d(H) \geq \frac\binom + r^(\ln)^n^,$

then contains a matching covering all but {{math, (''d'' – 1)''r'' 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.

References

Hypergraphs
Matching (graph theory)