Closing Gaps in Problems related to Hamilton Cycles in Random Graphs and Hypergraphs
Author:
Open Access
- 2 January 2015
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 22 (1) , P1.61
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\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). Bal and Frieze 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 w.h.p. one can find a rainbow Hamilton cycle where all the edges are directed in the same way.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Rainbow matchings and Hamilton cycles in random graphsRandom Structures & Algorithms, 2015
- Rainbow hamilton cycles in random graphsRandom Structures & Algorithms, 2013
- Optimal Divisibility Conditions for Loose Hamilton Cycles in Random HypergraphsThe Electronic Journal of Combinatorics, 2012
- Loose Hamilton Cycles in Random Uniform HypergraphsThe Electronic Journal of Combinatorics, 2011
- Loose Hamilton Cycles in Random 3-Uniform HypergraphsThe Electronic Journal of Combinatorics, 2010