Discrete Mathematics Seminar - The Erdős-Rothschild problem

Speaker: Katherine Staden (Open University)

Abstract:  Questions about forbidden subgraphs form a central part of extremal graph theory. In this talk I will discuss a colourful problem of this sort: the Erdős-Rothschild problem from 1974. Consider an n-vertex graph G whose edges are coloured with s colours so that there is no monochromatic clique of size k, and call such a colouring of G valid. The problem is to determine the maximum number of valid colourings over all n-vertex graphs G. It is in general wide open and an exact (or even asymptotic) answer is only known for a few pairs (k,s). In this talk I will discuss new exact results, and intriguing connections to algebra and designs.

Joint work with Oleg Pikhurko.