2016/02/16 by Deepak Bal, Patrick Bennett, Bal, Deepak +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1602.05169
openalex publication_date 2016/02/16 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
Given a graph on n vertices and an assignment of colours to the edges, a\nrainbow Hamilton cycle is a cycle of length n visiting each vertex once and\nwith pairwise different colours on the edges. Similarly (for even n) a\nrainbow perfect matching is a collection of n/2 independent edges with\npairwise different colours. In this note we show that if we randomly colour the\nedges of a random geometric graph with sufficiently many colours, then a.a.s.\nthe graph contains a rainbow perfect matching (rainbow Hamilton cycle) if and\nonly if the minimum degree is at least 1 (respectively, at least 2). More\nprecisely, consider n points (i.e. vertices) chosen independently and\nuniformly at random from the unit d-dimensional cube for any fixed d\≥2.\nForm a sequence of graphs on these n vertices by adding edges one by one\nbetween each possible pair of vertices. Edges are added in increasing order of\nlengths (measured with respect to the \ℓp norm, for any fixed\n1<p\≤\∞). Each time a new edge is added, it receives a random colour\nchosen uniformly at random and with repetition from a set of lceil Kn rceil\ncolours, where K=K(d) is a sufficiently large fixed constant. Then, a.a.s.\nthe first graph in the sequence with minimum degree at least 1 must contain a\nrainbow perfect matching (for even n), and the first graph with minimum\ndegree at least 2 must contain a rainbow Hamilton cycle.\n