Rainbow matchings and Hamilton cycles in random graphs

DOI10.1002/RSA.20594zbMATH Open1338.05209DBLPjournals/rsa/BalF16arXiv1311.6423OpenAlexW1937563492WikidataQ57401406 ScholiaQ57401406MaRDI QIDQ2811161FDOQ2811161

Authors: Deepak Bal, Alan Frieze 

Publication date: 10 June 2016

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Let $H{P}_{n,m,k}$ be drawn uniformly from all $k$-uniform, $k$-partite hypergraphs where each part of the partition is a disjoint copy of $[n]$. We let $H{P}_{n,m,k}^{(k)}$ be an edge colored version, where we color each edge randomly from one of $k$ colors. We show that if $k=n$ and $m=Knlogn$ where $K$ is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if $n$ is even and $m=Knlogn$ where $K$ is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in $G_{n,m}^{(n)}$. Here $G_{n,m}^{(n)}$ denotes a random edge coloring of $G_{n,m}$ with $n$ colors. When $n$ is odd, our proof requires $m=om(nlogn)$ for there to be a rainbow Hamilton cycle.

Full work available at URL: https://arxiv.org/abs/1311.6423

Recommendations

• Rainbow Hamilton cycles in random graphs and hypergraphs
• Rainbow Hamilton cycles in random graphs
• On rainbow Hamilton cycles in random hypergraphs
• Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs
• Rainbow Hamilton cycles in random regular graphs

zbMATH Keywords

perfect matchingsrandom hypergraphsrainbow coloringsLatin transversal

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Factors in random graphs
• Loose Hamilton cycles in random 3-uniform hypergraphs
• Lopsided Lovász Local lemma and Latin transversals
• Rainbow Hamilton cycles in random regular graphs
• Rainbow perfect matchings in complete bipartite graphs: existence and counting
• Rainbow Hamilton cycles in random graphs

Cited In (19)

• Elegantly colored paths and cycles in edge colored random graphs
• Pattern colored Hamilton cycles in random graphs
• Rainbow arborescence in random digraphs
• Rainbow perfect matchings and Hamilton cycles in the random geometric graph
• Multitrees in random graphs
• The threshold for the full perfect matching color profile in a random coloring of random graphs
• Colorful Hamilton Cycles in Random Graphs
• Rainbow thresholds
• On rainbow Hamilton cycles in random hypergraphs
• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• Rainbow Hamilton cycles in random graphs
• A note on rainbow matchings in strongly edge-colored graphs
• Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs
• Rainbow trees in uniformly edge‐colored graphs
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• Rainbow Hamilton cycles in random regular graphs
• Transversal Hamilton cycle in hypergraph systems
• Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs

This page was built for publication: Rainbow matchings and Hamilton cycles in random graphs

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