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

2015/02/05 by Ferber, Asaf · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1502.01399

Abstract

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≥ 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≥ (Klog 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.

Cited by

• On the diameter of random uniform hypergraphs in dense regime

Related

• Rainbow Hamilton cycles in random graphs
• On Rainbow Hamilton Cycles in Random Hypergraphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• Rainbow Hamilton cycles in randomly coloured randomly perturbed dense graphs
• A threshold result for loose Hamiltonicity in random regular uniform hypergraphs