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

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\geq 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 (w.h.p.) contains a loose Hamilton cycle, provided that $(k-1)|n$. This generalizes results of Frieze, Dudek and Frieze, and reproves a result of Dudek, Frieze, Loh and Speiss. Secondly, we show that there exists $K>0$ such for every $p\geq (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, w.h.p\ the resulting graph contains a Hamilton cycle with for which all the colors appear (a rainbow Hamilton cycle). 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 w.h.p.\ one can find a rainbow Hamilton cycle where all the edges are directed in the same way.

No reviews yet.

No comments yet.