file.pdf (413.74 kB)
0/0

Loose Hamilton Cycles in Regular Hypergraphs

Download (413.74 kB)
journal contribution
posted on 15.03.2013 by Andrzej Dudek, Alan Frieze, Andrzej Rucinski, Matas Sileikis

We establish a relation between two uniform models of random k-graphs (for constant k ≥ 3) on n labelled vertices: ℍ(k) (n,m), the random k-graph with exactly m edges, and ℍ (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 ~ cnd, then one can couple ℍ (k) (n,m) and ℍ (k) (n,d) so that the latter contains the former with probability tending to one as n → ∞. In view of known results on the existence of a loose Hamilton cycle in ℍ (k) (n,m), we conclude that ℍ (k) (n,d) contains a loose Hamilton cycle when d ≫ log n (or just dC log n, if k = 3) and d = o(n1/2).

History

Publisher Statement

© Cambridge University Press

Date

15/03/2013

Exports

Exports