### 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 |

### Fingerprint

### Keywords

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

### Cite this

*Random Structures and Algorithms*,

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

}

*Random Structures and Algorithms*, vol. 48, no. 3, pp. 503-523. https://doi.org/10.1002/rsa.20594

**Rainbow matchings and Hamilton cycles in random graphs.** / Bal, Deepak; Frieze, Alan.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - Rainbow matchings and Hamilton cycles in random graphs

AU - Bal, Deepak

AU - Frieze, Alan

PY - 2016/5/1

Y1 - 2016/5/1

N2 - Let HPn,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 HPn,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 Gn,m(n). Here Gn,m(n) denotes a random edge coloring of Gn,m with n colors. When n is odd, our proof requires m=ω(nlogn) for there to be a rainbow Hamilton cycle.

AB - Let HPn,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 HPn,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 Gn,m(n). Here Gn,m(n) denotes a random edge coloring of Gn,m with n colors. When n is odd, our proof requires m=ω(nlogn) for there to be a rainbow Hamilton cycle.

KW - Latin transversal

KW - Perfect matchings

KW - Rainbow colorings

KW - Random hypergraphs

UR - http://www.scopus.com/inward/record.url?scp=84961212812&partnerID=8YFLogxK

U2 - 10.1002/rsa.20594

DO - 10.1002/rsa.20594

M3 - Article

VL - 48

SP - 503

EP - 523

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 3

ER -