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

MaRDI QIDQ2260636zbMATH OpenFDO

Authors Asaf Ferber

Publication date 11 March 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.01399, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p61

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Hamilton cycleshypergraphsrandom graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

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 $kgeq3$, if $p{n}^{k-1}/logn$ 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 $pgeq(Klogn)/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))(logn)/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.

Review text

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.

Recommendations

• Rainbow Hamilton cycles in random graphs
• On rainbow Hamilton cycles in random hypergraphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs
• Rainbow matchings and Hamilton cycles in random graphs

Cites work

• Clutter percolation and random graphs
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Loose Hamilton cycles in random 3-uniform hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs
• Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
• Rainbow Hamilton cycles in random graphs
• Rainbow matchings and Hamilton cycles in random graphs

Cited in

(22)

• On rainbow Hamilton cycles in random hypergraphs
• On offset Hamilton cycles in random hypergraphs
• A threshold result for loose Hamiltonicity in random regular uniform hypergraphs
• Finding tight Hamilton cycles in random hypergraphs faster
• Rainbow matchings and Hamilton cycles in random graphs
• Spanning structures and universality in sparse hypergraphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• On spanning structures in random hypergraphs
• Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
• scientific article; zbMATH DE number 4031730 (Why is no real title available?)
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Packing loose Hamilton cycles
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Rainbow Hamilton cycles in random graphs
• Rainbow trees in uniformly edge‐colored graphs
• The hitting time of clique factors
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Rainbow subgraphs of uniformly coloured randomly perturbed graphs
• Rainbow Hamiltonicity in uniformly coloured perturbed digraphs
• The emergence of a giant rainbow component
• Rainbow spanning trees in uniformly coloured perturbed graphs (extended abstract)
• On rainbow thresholds

This page was built for publication: Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2260636)