| Full text | |
| Author(s): |
Total Authors: 4
|
| Affiliation: | [1] London Sch Econ, Dept Math, London WC2A 2AE - England
[2] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[3] Goethe Univ, Inst Math, D-60325 Frankfurt - Germany
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | RANDOM STRUCTURES & ALGORITHMS; v. 46, n. 3, p. 446-465, MAY 2015. |
| Web of Science Citations: | 7 |
| Abstract | |
We give an algorithmic proof for the existence of tight Hamilton cycles in a random r-uniform hypergraph with edge probability p=n-1+epsilon for every epsilon>0. This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374-385), who used a second moment method to show that tight Hamilton cycles exist even for p=(n)/n(r3) where (n) arbitrary slowly, and for p=(e+o(1))/n(r4). The method we develop for proving our result applies to related problems as well. (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 446-465, 2015 (AU) | |
| FAPESP's process: | 09/17831-7 - Embedding and packing problems in extremal graph theory |
| Grantee: | Julia Boettcher |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat |
| Grantee: | Oswaldo Baffa Filho |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 10/09555-7 - Embedding, randomised and structural problems in extremal graph theory |
| Grantee: | Peter David Allen |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |