Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
| Autor: | Vojtěch Rödl, Endre Szemerédi, Mathias Schacht, Christian Reiher, Andrzej Ruciński |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Hypergraph
Mathematics::Combinatorics Degree (graph theory) General Mathematics 010102 general mathematics 05C65 (05C45) 0102 computer and information sciences 16. Peace & justice 01 natural sciences Hamiltonian path Upper and lower bounds Combinatorics symbols.namesake Asymptotically optimal algorithm 010201 computation theory & mathematics FOS: Mathematics symbols Mathematics - Combinatorics Combinatorics (math.CO) 0101 mathematics Hamiltonian (control theory) Mathematics |
| Zdroj: | Proceedings of the London Mathematical Society. 119:409-439 |
| ISSN: | 1460-244X 0024-6115 |
| DOI: | 10.1112/plms.12235 |
| Popis: | We show that every 3-uniform hypergraph with $n$ vertices and minimum vertex degree at least $(5/9+o(1))\binom{n}2$ contains a tight Hamiltonian cycle. Known lower bound constructions show that this degree condition is asymptotically optimal. 38 pages, second version addresses changes arising from the referee reports |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text