Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity

详细信息    查看全文

• 作者：Andrzej Dudek^a ; ¹ ; ⁵ ; Alan Frieze^b ; ² ; Andrzej Ruciński^c ; ³ ; ⁵ ; Matas &Scaron ; ileikis^d ; ⁴ ; ⁵ ; ^{matas.sileikis@gmail.com}
• 关键词：Random regular graph ; Random hypergraph ; Hamilton cycle ; Monotone graph property
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：719-740
• 全文大小：500 K
• 卷排序：122

文摘

We establish an inclusion relation between two uniform models of random k  -graphs (for constant k≥2k≥2) on n   labeled vertices: G(k)(n,m)G(k)(n,m), the random k-graph with m   edges, and R(k)(n,d)R(k)(n,d), the random d-regular k  -graph. We show that if nlog⁡n≪m≪nknlog⁡n≪m≪nk we can choose d=d(n)∼km/nd=d(n)∼km/n and couple G(k)(n,m)G(k)(n,m) and R(k)(n,d)R(k)(n,d) so that the latter contains the former with probability tending to one as n→∞n→∞. This extends an earlier result of Kim and Vu about “sandwiching random graphs”. In view of known threshold theorems on the existence of different types of Hamilton cycles in G(k)(n,m)G(k)(n,m), our result allows us to find conditions under which R(k)(n,d)R(k)(n,d) is Hamiltonian. In particular, for k≥3k≥3 we conclude that if nk−2≪d≪nk−1nk−2≪d≪nk−1, then a.a.s. R(k)(n,d)R(k)(n,d) contains a tight Hamilton cycle.