The two-thirds conjecture

6 May 2014
John Talbot

Erdos, Faudree, Gould, Gyarfas, Rousseau and Schelp, conjectured that
whenever the edges of a complete graph are coloured using three colours
there always exists a set of at most three vertices which have at least
two-thirds of their neighbours in one of the colours.  We will describe a
proof of this conjecture. This is joint work with Rahil Baber

  • Combinatorial Theory Seminar