Loose Hamilton Cycles in Regular Hypergraphs. (24th September 2014)

• Record Type: Journal Article
• Authors: DUDEK, ANDRZEJ; FRIEZE, ALAN; RUCIŃSKI, ANDRZEJ; ŠILEIKIS, MATAS
• Editors: Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 1(2015:Jan.)
• Page Start: 179
• Page End: 194
• Publication Date: 2014-09-24
• Subjects: Primary 05C65, -- 05C80, -- Secondary 05C38; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000406
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : 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 d ⩾ C log n, if k = 3) and d = o ( n 1/2 ).