Algorithms, Combinatorics and Optimization Seminar Bhargav Narayanan
University of Cambridge
Title: Exactly m-coloured graphs

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 na. In this talk, I will talk about this theorem and various other related questions and results.

Date: Thursday, April 3, 2014
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Boris Bukh