A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs. (18th October 2013)

• Record Type: Journal Article
• Authors: KITTIPASSORN, TEERADEJ; NARAYANAN, BHARGAV P.
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 1(2014:Jan.)
• Page Start: 102
• Page End: 115
• Publication Date: 2013-10-18
• Subjects: Primary 05C55, -- Secondary 05C63; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548313000503
• Languages: English
• ISSNs: 0963-5483

Abstract

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.