Rainbow perfect matchings and Hamilton cycles in the random geometric graph.
Given a graph on n vertices and an assignment of colors to the edges, a rainbow Hamilton cycle is a cycle of length n visiting each vertex once and with pairwise different colors on the edges. Rainbow perfect matchings are defined analogously. We claim that if we randomly color the edges of a random geometric graph with sufficiently many colors, then a.a.s. the graph contains a rainbow perfect matching (rainbow Hamilton cycle) if and only if the minimum degree is at least 1 (respectively, at least 2). More precisely, consider n points (i.e. vertices) chosen independently and uniformly at random from the unit d-dimensional cube for any fixed d≥2. Form a sequence of graphs on these n vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of lengths. Each time a new edge is added, it receives a random color chosen uniformly at random and with repetition from a set of ⌈Kn⌉ colors, where K=K(d) is a sufficiently large fixed constant. Then, a.a.s. the first graph in the sequence with minimum degree at least 1 must contain a rainbow perfect matching (for even n), and the first graph with minimum degree at least 2 must contain a rainbow Hamilton cycle.
This is joint work with Deepak Bal, Patrick Bennett and Paweł Prałat.