Monochromatic cycle partitions

Monochromatic cycle partitions

-
Maya Stein , University of Chile
Fine Hall 224

Given a complete graph on n vertices, whose edges are coloured with r colours, our aim is to find a small set of disjoint monochromatic cycles which together cover all the vertices. (Edges and single vertices count as cycles here.) It turns out that the number of cycles needed depends only on r (the number of colours) and not on n (the order of the graph). This was shown in 1991 by Erdos, Gyarfas and Pyber: there is a function f(r) such that for every r-colouring of the edges of K_n, there are f(r) vertex-disjoint monochromatic cycles, which together cover all the vertices. The problem of determining f(r), and variations of the monochromatic cycle cover problem have attracted much interest in recent years. We generalise the result of Erdos, Gyarfas and Pyber to r-local colourings, and discuss extensions of the problem to graphs of large minimum degree. This is based on joint work with David Conlon, with Richard Lang, and with Peter Allen, Julia Boettcher, Richard Lang and Jozef Skokan.