Rainbow matchings and Hamilton cycles in random graphs |
| |
Authors: | Deepak Bal Alan Frieze |
| |
Institution: | 1. Department of Mathematics, Miami University, Oxford, Ohio;2. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennyslvania |
| |
Abstract: | Let be drawn uniformly from all m‐edge, k‐uniform, k‐partite hypergraphs where each part of the partition is a disjoint copy of . We let be an edge colored version, where we color each edge randomly from one of colors. We show that if and 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 where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in . Here denotes a random edge coloring of with n colors. When n is odd, our proof requires for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016 |
| |
Keywords: | random hypergraphs perfect matchings rainbow colorings latin transversal |
|
|