Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T11:31:28.804Z Has data issue: false hasContentIssue false
  • English
  • Français

A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs

Published online by Cambridge University Press:  18 October 2013

TEERADEJ KITTIPASSORN  and
BHARGAV P. NARAYANAN
TEERADEJ KITTIPASSORN
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA (e-mail: t.kittipassorn@memphis.edu)
BHARGAV P. NARAYANAN
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: b.p.narayanan@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Keywords

Primary 05C55Secondary 05C63

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 1 , January 2014 , pp. 102 - 115
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Erdős, P. and Rado, R. (1950) A combinatorial theorem. J. London Math. Soc. 25 249–255.CrossRefGoogle Scholar
[2]Erickson, M. (1994) A conjecture concerning Ramsey's theorem. Discrete Math. 126 395–398.Google Scholar
[3]Graham, R. L., Rothschild, B. L. and Spencer, J. H. (1980) Ramsey Theory, Wiley-Interscience Series in Discrete Mathematics, Wiley.Google Scholar
[4]Gyárfás, A. (2002) Transitive edge coloring of graphs and dimension of lattices. Combinatorica 22 479–496.Google Scholar
[5]Hindman, N., Leader, I. and Strauss, D. (2006) Forbidden distances in the rationals and the reals. J. London Math. Soc. 73 273–286.CrossRefGoogle Scholar
[6]Laflamme, C., Sauer, N. W. and Vuksanovic, V. (2006) Canonical partitions of universal structures. Combinatorica 26 183–205.CrossRefGoogle Scholar
[7]Larson, J. A. (2008) Counting canonical partitions in the random graph. Combinatorica 28 659–678.Google Scholar
[8]Narayanan, B. P. (2013) Exactly m-coloured complete infinite subgraphs. Submitted. arxiv.org:1303.2997.Google Scholar
[9]Ramsey, F. P. (1930) On a problem of formal logic. Proc. London Math. Soc. 30 264–286.Google Scholar
[10]Stacey, A. and Weidl, P. (1999) The existence of exactly m-coloured complete subgraphs. J. Combin. Theory Ser. B 75 1–18.Google Scholar