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

For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University.

Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...)


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