Matematiska institutionen

Sannolikhets- och statistikseminarium: Colouring Hamilton Cycles Online

  • Datum:
  • Plats: Ångströmlaboratoriet 64119
  • Föreläsare: Joe Briggs, Carnegie Mellon University
  • Kontaktperson: Tony Johansson
  • Seminarium

Abstract: One classical theorem in the history of random graphs tells us that the threshold probability in G_{n,p} for Hamiltonicity (as n tends to infinity) is the same as that for having minimum degree 2. Translating to the discrete random graph process G_0, G_1, ... , G_m, ... allowed this result to be fine-tuned in a very strong sense: in fact, the first graph G_{t_2} with minimum degree 2 is already Hamiltonian w.h.p. Furthermore, Bollobás and Frieze showed that the first graph G_{t_{2q}} with minimum degree 2q contained q edge-disjoint Hamilton cycles, for any fixed q. In other words, G_{t_{2q}} can be q-edge-coloured in such a way that each colour class is Hamiltonian.

We extend this classical result even further by imposing an online restriction on the desired colouring, reflecting the dynamic nature of the random graph process. We are forced to commit to the colour of each new edge as it is revealed, with no knowledge of which edges will appear thereafter. In this talk I will describe a q-colouring process that still succeeds under these limitations. When the edges of the random graph process are coloured online according to this algorithm, then G_{t_{2q}} has a Hamilton cycle in every colour w.h.p.

This is joint work with Alan Frieze, Michael Krivelevich, Po-Shen Loh, and Benny Sudakov.