Name
Abstract | ||
|---|---|---|
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(kappa) be an edge colored version, where we color each edge randomly from one of kappa colors. We show that if kappa = n and m = Kn 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 = Kn log n 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 =omega(n log n) for there to be a rainbow Hamilton cycle. (C) 2015 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/rsa.20594 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
random hypergraphs,perfect matchings,rainbow colorings,latin transversal | Discrete mathematics,Edge coloring,Combinatorics,Disjoint sets,Random graph,Hamiltonian path,Constraint graph,Matching (graph theory),Partition (number theory),Rainbow,Mathematics | Journal |
Volume | Issue | ISSN |
48.0 | 3.0 | 1042-9832 |
Citations | PageRank | References |
7 | 0.66 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deepak Bal | 1 | 35 | 7.32 |
| Alan M. Frieze | 2 | 4837 | 787.00 |