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