Minimum degree of 3-graphs without long linear paths

摘要

A well known theorem in graph theory states that every graph G on n vertices and minimum degree at least d contains a path of length at least d, and if G is connected and n >= 2d+ 1 then G contains a path of length at least 2d (Dirac, 1952). In this article, we give an extension of Dirac's result to hypergraphs. We determine asymptotic lower bounds of the minimum degrees of 3-graphs to guarantee linear paths of specific lengths, and the lower bounds are tight up to an error term depending only on the lengths of the paths. (C) 2020 Elsevier B.V. All rights reserved.