The ACO Seminar (2013–2014)

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.