Vertex Degree Sums for Perfect Matchings in 3-Uniform Hypergraphs

  • Yi Zhang
  • Yi Zhao
  • Mei Lu
Keywords: Perfect matchings, Hypergraphs, Dirac's theorem, Ore's condition

Abstract

We determine the minimum degree sum of two adjacent vertices that ensures a perfect matching in a 3-uniform hypergraph without an isolated vertex. Suppose that $H$ is a 3-uniform hypergraph whose order $n$ is sufficiently large and divisible by $3$. If $H$ contains no isolated vertex and $\deg(u)+\deg(v) > \frac{2}{3}n^2-\frac{8}{3}n+2$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $H$ contains a perfect matching. This bound is tight and the (unique) extremal hyergraph is a different space barrier from the one for the corresponding Dirac problem.

Published
2018-09-07
Article Number
P3.45