A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs. (January 2014)

• 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: 2014-01
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548313000503
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>Given an edge <italic>colouring</italic> of a graph with a set of <italic>m colours</italic>, we say that the graph is <italic>exactly m-coloured</italic> if each of the <italic>colours</italic> is used. We consider edge colourings of the complete graph on <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh350fdfg9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{N}$]]></tex-math></alternatives></inline-formula> with infinitely many colours and show that either one can find an exactly <italic>m</italic>-coloured complete subgraph for every natural number <italic>m</italic> or there exists an infinite subset <italic>X</italic> ⊂ <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgh350fdfg9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\mathbb{N}$]]></tex-math></alternatives></inline-formula> coloured in one of two canonical ways: either the colouring is injective on <italic>X</italic> or there exists a distinguished vertex <italic>v</italic> in <italic>X</italic> such that <italic>X</italic>\{<italic>v</italic>} is 1-coloured and each edge between <italic>v</italic> and <italic>X</italic>\{<italic>v</italic>} has a distinct colour (all different to the colour used on <italic>X</italic>\{<italic>v</italic>}). 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 <italic>m</italic>-coloured complete subgraphs in colourings with finitely many colours.</p> </abstract>