2015/02/04 by Asaf Ferber, Ferber, Asaf · 2 citations
Mathematics · #Advanced Topology and Set Theory #Binary logarithm #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #FOS: Mathematics #Graph #Hamiltonian path #Hypergraph #Infinity #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Random graph #math.CO
paper · pdf · doi:10.48550/arxiv.1502.01399
published in arXiv (Cornell University) (Cornell University) · 5 pages
openalex publication_date 2015/02/04 · arxiv created 2015/02/06 · arxiv updated 2015/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We show how to adjust a very nice coupling argument due to McDiarmid in order\nto prove/reprove in a novel way results concerning Hamilton cycles in various\nmodels of random graph and hypergraphs. In particular, we firstly show that for\nk\≥ 3, if pnk-1/\log n tends to infinity, then a random k-uniform\nhypergraph on n vertices, with edge probability p, with high probability\n(w.h.p.) contains a loose Hamilton cycle, provided that (k-1)|n. This\ngeneralizes results of Frieze, Dudek and Frieze, and reproves a result of\nDudek, Frieze, Loh and Speiss. Secondly, we show that there exists K>0 such\nfor every p\≥ (K\log n)/n the following holds: Let Gn,p be a random\ngraph on n vertices with edge probability p, and suppose that its edges are\nbeing colored with n colors uniformly at random. Then, w.h.p the resulting\ngraph contains a Hamilton cycle with for which all the colors appear (a rainbow\nHamilton cycle). Lastly, we show that for p=(1+o(1))(\log n)/n, if we\nrandomly color the edge set of a random directed graph Dn,p with\n(1+o(1))n colors, then w.h.p. one can find a rainbow Hamilton cycle where\nall the edges are directed in the same way.\n