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

作者：Roedl Vojtech; Rucinski Andrzej^*; Szemeredi Endre

来源：Advances in Mathematics, 2011, 227(3): 1225-1299.

DOI：10.1016/j.aim.2011.03.007

• Hamilton cycle
• Hypergraph

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 n(0) such that every n-vertex 3-uniform hypergraph H, n >= n(0), in which each pair of vertices belongs to at least n/2 1 (Ln/2J) edges, contains a hamiltonian path (cycle, respectively). Both results are easily seen to be optimal.

• 出版日期2011-6-20