### Abstract

Let HP_{n,m,k} be drawn uniformly from all m-edge, k-uniform, k-partite hypergraphs where each part of the partition is a disjoint copy of [n]. We let HP_{n,m,k}(^{κ}) be an edge colored version, where we color each edge randomly from one of κ colors. We show that if κ=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=ω(nlogn) for there to be a rainbow Hamilton cycle.

Original language | English |
---|---|

Pages (from-to) | 503-523 |

Number of pages | 21 |

Journal | Random Structures and Algorithms |

Volume | 48 |

Issue number | 3 |

DOIs | |

State | Published - 1 May 2016 |

### Keywords

- Latin transversal
- Perfect matchings
- Rainbow colorings
- Random hypergraphs

## Fingerprint Dive into the research topics of 'Rainbow matchings and Hamilton cycles in random graphs'. Together they form a unique fingerprint.

## Cite this

*Random Structures and Algorithms*,

*48*(3), 503-523. https://doi.org/10.1002/rsa.20594