*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 14th April, 3:00 in Fine Hall 224. Speaker: Maya Stein (University of Chile) Title: Monochromatic cycle partitions 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. ----------- Next week: Oliver Schaudt Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)