Name
Abstract | ||
|---|---|---|
We establish a relation between two uniform models of random k-graphs (for constant k >= 3) on n labelled vertices: H-(k)(n, m), the random k-graph with exactly m edges, and H-(k)(n, d), the random d-regular k-graph. By extending the switching technique of McKay and Wormald to k-graphs, we show that, for some range of d = d(n) and a constant c > 0, if m similar to cnd, then one can couple H-(k)(n, m) and H-(k)(n, d) so that the latter contains the former with probability tending to one as n -> infinity. In view of known results on the existence of a loose Hamilton cycle in H-(k)(n, m), we conclude that H-(k)(n, d) contains a loose Hamilton cycle when d >> log n (or just d >= C log n, if k = 3) and d = o(n(1/ 2)). |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1017/S0963548314000406 | COMBINATORICS PROBABILITY & COMPUTING |
Keywords | Field | DocType |
mathematics | Discrete mathematics,Combinatorics,Vertex (geometry),Hamiltonian path,Constraint graph,Mathematics | Journal |
Volume | Issue | ISSN |
24 | SP1 | 0963-5483 |
Citations | PageRank | References |
1 | 0.36 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 114 | 23.10 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Andrzej Ruciński | 3 | 420 | 51.89 |
| Matas Sileikis | 4 | 6 | 3.15 |