Apr. 3, 3:30pm, Wean 8220

Bhargav Narayanan, University of Cambridge

Exactly*m*-coloured graphs

Bhargav Narayanan, University of Cambridge

Exactly

Abstract:

Given an edge-colouring of a graph with a set of m colours, we say that the graph is
exactly *m*-coloured if each of the colours is used. If we are given an edge-colouring
of the complete graph on the natural numbers with infinitely many colours, for which
numbers *m* can one always find an exactly m-coloured complete subgraph? Stacey and
Weidl asked this question in 1999, noting that the injective colouring leaves only
numbers of the form *n*(*n*-*1*)/*2* as potential candidates. Teeradej Kittipassorn and I
answered this question recently; we proved that whenever the complete graph on the
natural numbers is coloured with infinitely many colours, there is a complete
(*n*(*n*-*1*)/*2*)-coloured subgraph for every natural number *n*. In this talk, I will talk
about this theorem and various other related questions and results.