Dirac-type conditions for hamiltonian paths and cycles in 3-uniform hypergraphs
By Vojtech Rödl, Andrzej Rucinski, Endre Szemerédi. 2011
98 citations recorded by the source corpus.
Abstract 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 ( ⌊ n / 2 ⌋ ) edges, contains a hamiltonian path (cycle, respectively). Both results are easily seen to be optimal.
Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering
View Paper: https://www.semanticscholar.org/paper/58f6b9dea856a76dc9dd7ddf74fc52f936102472
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Discrete Mathematics and Combinatorics
In Electrical and Electronic Engineering
Citations in the corpus
- Hamilton cycles in graphs and hypergraphs: an extremal perspective (2014, background): “A Dirac-type theorem for tight Hamilton cycles was proved by Rödl, Ruciński and Szemerédi [129, 130].”
- Recent advances on Dirac-type problems for hypergraphs (2015, background): “On the other hand, since the extremal cases in [33, 74] require involved work, it seems harder to determine the exact value of hl(k, n) when k − l divides k.”