Rainbow perfect matchings and Hamilton cycles in the random geometric graph1. Issue 4 (5th April 2017)

• Record Type: Journal Article
• Authors: Bal, Deepak; Bennett, Patrick; Pérez‐Giménez, Xavier; Prałat, Paweł
• Is Part Of: Random structures & algorithms. Volume 51:Issue 4(2017)
• Page Start: 587
• Page End: 606
• Publication Date: 2017-04-05
• Subjects: perfect matchings -- Hamilton cycles -- random geometric graphs -- rainbow; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20717
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Given a graph on n vertices and an assignment of colours to the edges, a rainbow Hamilton cycle is a cycle of length n visiting each vertex once and with pairwise different colours on the edges. Similarly (for even n ) a rainbow perfect matching is a collection of n / 2 independent edges with pairwise different colours. In this note we show that if we randomly colour the edges of a random geometric graph with sufficiently many colours, 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 (measured with respect to the ℓ p norm, for any fixed 1 < p ≤ ∞ ). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of ⌈ K n ⌉ colours, where K = K ( d ) 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. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 587–606, 2017