Premium
Rainbow matchings and Hamilton cycles in random graphs
Author(s) -
Bal Deepak,
Frieze Alan
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20594
Subject(s) - rainbow , combinatorics , colored , mathematics , partition (number theory) , disjoint sets , edge coloring , enhanced data rates for gsm evolution , matching (statistics) , discrete mathematics , graph , physics , computer science , line graph , artificial intelligence , optics , statistics , materials science , graph power , composite material
Abstract Let H P n , m , kbe 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 H P 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 = K n log n 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 = K n log n where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle inG n , m ( n ). HereG n , m ( n )denotes a random edge coloring ofG n , mwith n colors. When n is odd, our proof requires m = ω ( n log n ) for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016