Rainbow matchings and Hamilton cycles in random graphs

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

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

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 (16)

• Rainbow arborescence in random digraphs
• Multitrees in random graphs
• The threshold for the full perfect matching color profile in a random coloring of random graphs
• Rainbow Hamilton Cycles in Randomly Colored Randomly Perturbed Dense Graphs
• Pattern Colored Hamilton Cycles in Random Graphs
• Elegantly Colored Paths and Cycles in Edge Colored 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
• 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 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)