Portal de Periódicos da CAPES

Dirac-type conditions for hamiltonian paths and cycles in 3-uniform hypergraphs

2011; Elsevier BV; Volume: 227; Issue: 3 Linguagem: Inglês

10.1016/j.aim.2011.03.007

1090-2082

Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi,

Finite Group Theory Research

A hamiltonian path (cycle) in an n-vertex 3-uniform hypergraph is a (cyclic) ordering of the vertices in which every three consecutive vertices form an edge. For large n, we prove an analog of the celebrated Dirac theorem for graphs: there exists n0 such that every n-vertex 3-uniform hypergraph H, n⩾n0, in which each pair of vertices belongs to at least n/2−1 (⌊n/2⌋) edges, contains a hamiltonian path (cycle, respectively). Both results are easily seen to be optimal.