pith. sign in

arxiv: 1602.05169 · v1 · pith:HGLTHXOSnew · submitted 2016-02-16 · 🧮 math.CO

Rainbow perfect matchings and Hamilton cycles in the random geometric graph

classification 🧮 math.CO
keywords rainbowedgesgraphcoloursrandomcyclehamiltonleast
0
0 comments X
read the original 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\ge2$. 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 $\ell_p$ norm, for any fixed $1<p\le\infty$). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of $\lceil Kn\rceil$ colours, 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 paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.