CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
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