Minimum degree condition of Berge Hamiltonicity in random 3-uniform hypergraphs


Ailian Chen, Liping Zhang




A graph H has Hamiltonicity if it contains a cycle which covers each vertex of H. In graph theory , Hamiltonicity is a classical and worth studying problem. In 1952, Dirac proved that any n-vertex graph H with minimum degree at least ⌈ n 2 ⌉ has Hamiltonicity. In 2012, Lee and Sudakov proved that if p ≫ log n n , then asympotically almost surely each n-vertex subgraph of random graph G(n, p) with minimum degree at least (1/2 + o(1))np has Hamiltonicity. In this paper, we exend Dirac's theorem to random 3-uniform hypergraphs. The random 3-uniform hypergraph model H 3 (n, p) consists of all 3-uniform hypergraphs on n vertices and every possible edge appears with probability p randomly and independently. We prove that if p ≫ log n n 2 , then asympotically almost surely every n-vertex subgraph of H 3 (n, p) with minimum degree at least (1 4 + o(1))(n 2)p has Berge Hamiltonicity. The value log n n 2 and constant 1/4 both are best possible.