Essentially infinite colourings of hypergraphs

We consider edge colourings of the complete r-uniform hypergraph K n(r)on n vertices. How many colours may such a colouring have if we restrict the number of colours locally? The local restriction is formulated as follows: for a fixed hypergraph H and an integer k we call a colouring (H, k)-local if every copy of H in the complete hypergraph K n(r) receives at most k different colours.We investigate the threshold for k that guarantees that every (H, k)-local colouring of K n(r) must have a globally bounded number of colours as n → ∞, and we establish this threshold exactly. The following phenomenon is also observed: for many H (at least in the case of graphs), if k is a little over this threshold, the unbounded (H, k)-local colourings exhibit their colourfulness in a \u27sparse way\u27; more precisely, a bounded number of colours are dominant while all other colours are rare. Hence we study the threshold k0 for k that guarantees that every (H, k)-local colouring γn of Kn(r) with k ≤ k0 must have a globally bounded number of colours after the deletion of up to εnr edges for any fixed ε \u3e 0 (the bound on the number of colours is allowed to depend on H and ε only); we think of such colourings γn as \u27essentially finite\u27. As it turns out, every essentially infinite colouring is closely related to a non-monochromatic canonical Ramsey colouring of Erdös and Rado. This second threshold is determined up to an additive error of 1 for every hypergraph H. Our results extend earlier work for graphs by Clapsadle and Schelp [\u27Local edge colorings that are global\u27, J. Graph Theory 18 (1994) 389-399] and by the first two authors and Schelp [\u27Essentially infinite colourings of graphs\u27, J. London Math. Soc. (2) 61 (2000) 658-670]. We also consider a related question for colourings of the integers and arithmetic progressions. © 2007 London Mathematical Society