Abstract | ||
---|---|---|
In the random k-uniform hypergraph H-n,p((k)), of order n, each possible k-tuple appears independently with probability p. A loose Hamilton cycle is a cycle of order n in which every pair of consecutive edges intersects in a single vertex. It was shown by Frieze that if p >= c(log n)/n(2) for some absolute constant c > 0, then a.a.s. Hn(3,p) contains a loose Hamilton cycle, provided that n is divisible by 4. Subsequently, Dudek and Frieze extended this result for any uniformity k >= 4, proving that if p >> (log n)/n(k-1), then H-n,p((k)) contains a loose Hamilton cycle, provided that n is divisible by 2(k - 1). In this paper, we improve the divisibility requirement and show that in the above results it is enough to assume that n is a multiple of k - 1, which is best possible. |
Year | Venue | Field |
---|---|---|
2012 | ELECTRONIC JOURNAL OF COMBINATORICS | Binary logarithm,Discrete mathematics,Combinatorics,Vertex (geometry),Divisibility rule,Hamiltonian path,Hypergraph,Constraint graph,Mathematics |
DocType | Volume | Issue |
Journal | 19.0 | 4.0 |
ISSN | Citations | PageRank |
1077-8926 | 10 | 0.69 |
References | Authors | |
10 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrzej Dudek | 1 | 114 | 23.10 |
Alan M. Frieze | 2 | 4837 | 787.00 |
Po-Shen Loh | 3 | 133 | 18.68 |
Shelley Speiss | 4 | 10 | 0.69 |