Rainbow perfect matchings and Hamilton cycles in the random geometric graph

Deepak Bal, Patrick Bennett, Xavier Pérez-Giménez, Paweł Prałat

Research output: Contribution to journalArticle

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 lp 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 Kn 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.

Original languageEnglish
Pages (from-to)587-606
Number of pages20
JournalRandom Structures and Algorithms
Volume51
Issue number4
DOIs
StatePublished - 1 Dec 2017

Fingerprint

Random Geometric Graph
Hamilton Cycle
Perfect Matching
Color
Minimum Degree
Graph in graph theory
Pairwise
Lp-norm
Regular hexahedron
Assignment
If and only if
Cycle
Unit
Vertex of a graph

Keywords

  • Hamilton cycles
  • perfect matchings
  • rainbow
  • random geometric graphs

Cite this

Bal, Deepak ; Bennett, Patrick ; Pérez-Giménez, Xavier ; Prałat, Paweł. / Rainbow perfect matchings and Hamilton cycles in the random geometric graph. In: Random Structures and Algorithms. 2017 ; Vol. 51, No. 4. pp. 587-606.
@article{f8c965878f23413d8683862000a428ed,
title = "Rainbow perfect matchings and Hamilton cycles in the random geometric graph",
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 lp norm, for any fixed 1",
keywords = "Hamilton cycles, perfect matchings, rainbow, random geometric graphs",
author = "Deepak Bal and Patrick Bennett and Xavier P{\'e}rez-Gim{\'e}nez and Paweł Prałat",
year = "2017",
month = "12",
day = "1",
doi = "10.1002/rsa.20717",
language = "English",
volume = "51",
pages = "587--606",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Ltd",
number = "4",

}

Rainbow perfect matchings and Hamilton cycles in the random geometric graph. / Bal, Deepak; Bennett, Patrick; Pérez-Giménez, Xavier; Prałat, Paweł.

In: Random Structures and Algorithms, Vol. 51, No. 4, 01.12.2017, p. 587-606.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Rainbow perfect matchings and Hamilton cycles in the random geometric graph

AU - Bal, Deepak

AU - Bennett, Patrick

AU - Pérez-Giménez, Xavier

AU - Prałat, Paweł

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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 lp norm, for any fixed 1

AB - 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 lp norm, for any fixed 1

KW - Hamilton cycles

KW - perfect matchings

KW - rainbow

KW - random geometric graphs

UR - http://www.scopus.com/inward/record.url?scp=85017206328&partnerID=8YFLogxK

U2 - 10.1002/rsa.20717

DO - 10.1002/rsa.20717

M3 - Article

AN - SCOPUS:85017206328

VL - 51

SP - 587

EP - 606

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 4

ER -