Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs (Q2260636)

Summary: We show how to adjust a very nice coupling argument due to McDiarmid in order to prove/reprove in a novel way results concerning Hamilton cycles in various models of random graph and hypergraphs. In particular, we firstly show that for \(k\geqslant 3\), if \(pn^{k-1}/\log n\) tends to infinity, then a random \(k\)-uniform hypergraph on \(n\) vertices, with edge probability \(p\), with high probability contains a loose Hamilton cycle, provided that \((k-1)|n\). This generalizes results of \textit{A. Dudek} and \textit{A. Frieze} [Electron. J. Comb. 18, No. 1, Research Paper P48, 14 p. (2011; Zbl 1218.05174)] and \textit{A. Frieze} [Electron. J. Comb. 17, No. 1, Research Paper N28, 4 p. (2010; Zbl 1189.05117)], and reproves a result of \textit{A. Dudek} et al. [Electron. J. Comb. 19, No. 4, Research Paper P44, 17 p., electronic only (2012; Zbl 1266.05152)]. Secondly, we show that there exists \(K>0\) such for every \(p\geqslant (K\log n)/n\) the following holds: Let \(G_{n,p}\) be a random graph on \(n\) vertices with edge probability \(p\), and suppose that its edges are being colored with~\(n\) colors uniformly at random. Then, with high probability the resulting graph contains a Hamilton cycle with for which all the colors appear (a rainbow Hamilton cycle). \textit{D. Bal} and \textit{A. Frieze} [``Rainbow matchings and Hamilton cycles in random graphs'', Preprint, \url{arXiv:1311.6423}] proved the latter statement~for graphs on an even number of vertices, where for odd \(n\) their \(p\) was \(\omega((\log n)/n)\). Lastly, we show that for \(p=(1+o(1))(\log n)/n\), if we randomly color the edge set of a~random directed graph \(D_{n,p}\) with \((1+o(1))n\) colors, then with high probability one can find a rainbow Hamilton cycle where all the edges~are directed in the same way.