file.pdf (413.74 kB)

Download file# Loose Hamilton Cycles in Regular Hypergraphs

journal contribution

posted on 15.03.2013, 00:00 authored by Andrzej Dudek, Alan FriezeAlan Frieze, Andrzej Rucinski, Matas SileikisWe 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 *d* ≥ *C* log *n*, if *k* = 3) and *d* = *o*(*n*^{1/2}).