A Dirac-type theorem for uniform hypergraphs

Abstract

Dirac (1952) proved that every connected graph of order $n>2k+1$ with minimum degree more than $k$ contains a path of length at least $2k+1$. Erdős and Gallai (1959) showed that every $n$-vertex graph $G$ with average degree more than $k-1$ contains a path of length $k$. The hypergraph extension of the Erdős-Gallai Theorem have been given by Győri, Katona, Lemons~(2016) and Davoodi et al.~(2018). Füredi, Kostochka, and Luo (2019) gave a connected version of the Erdős-Gallai Theorem for hypergraphs. In this paper, we give a hypergraph extension of the Dirac's Theorem: Given positive integers $n,k$ and $r$, let $H$ be a connected $n$-vertex $r$-graph with no Berge path of length $2k+1$. We show that (1) If $k>r\ge 4$ and $n>2k+1$, then ${\delta }_1(H)\le \left(\genfrac{}{}{0ex}{}{k}{r-1}\right)$. Furthermore, the equality holds if and only if $S_r^{\prime }(n,k)\subseteq H\subseteq S_r(n,k)$ or $H\cong S(s{K}_{k+1}^{(r)},1)$; (2) If $k\ge r\ge 2$ and $n>2k(r-1)$, then ${\delta }_1(H)\le \left(\genfrac{}{}{0ex}{}{k}{r-1}\right)$. The result is also a Dirac-type version of the result of Füredi, Kostochka, and Luo. As an application of (1), we give a better lower bound of the minimum degree than the ones in the Dirac-type results for Berge Hamiltonian cycle given by Bermond et al.~(1976) and Clemens et al. (2016), respectively.

23 pages

References in corpus (1)

• An Erdős-Gallai type theorem for uniform hypergraphs