A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs. (18th October 2013) - KITTIPASSORN, TEERADEJ; NARAYANAN, BHARGAV P.
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. We consider edge colourings of the complete graph on $\mathbb{N}$ with infinitely many colours and show that either one can find an exactly m -coloured complete subgraph for every natural number m or there exists an infinite subset X ⊂ $\mathbb{N}$ coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex v in X such that X \{ v } is 1-coloured and each edge between v and X \{ v } has a distinct colour (all different to the colour used on X \{ v }). This answers a question posed by Stacey and Weidl in 1999. The techniques that we develop also enable us to resolve some further questions about finding exactly m -coloured complete subgraphs in colourings with finitely many colours.