Essentially infinite colourings of graphs

Citation
B. Bollobas et al., Essentially infinite colourings of graphs, J LOND MATH, 61, 2000, pp. 658-670
Citations number
11
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES
ISSN journal
00246107 → ACNP
Volume
61
Year of publication
2000
Part
3
Pages
658 - 670
Database
ISI
SICI code
0024-6107(200006)61:<658:EICOG>2.0.ZU;2-Q
Abstract
The classical canonical Ramsey theorem of Erdos and Rado states that, for a ny integer q greater than or equal to 1, any edge colouring of a large enou gh complete graph contains one of three canonically coloured complete subgr aphs of order q. Of these canonical subgraphs, one is coloured monochromati cally while each of the other two has its edge set coloured with many diffe rent colours. The paper presents a condition on colourings that, roughly sp eaking, requires them to make effective use of many colours ('essential inf initeness'); this condition is then shown to imply that the colourings in q uestion must contain large refinements of one of two 'unavoidable' colourin gs that are rich in colours. As it turns out, one of these unavoidable colo urings is one of the canonical colourings of Erdos and Rado, and the other is a 'bipartite variant' of this colouring.