Proceedings of the London Mathematical Society Advance Access originally published online on July 19, 2007
Proceedings of the London Mathematical Society 2007 95(3):709-734; doi:10.1112/plms/pdm024
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
© 2007 London Mathematical Society
Essentially infinite colourings of hypergraphs
Department of Mathematical Sciences
University of Memphis
Memphis, TN 38152
USA
and
Trinity College
Cambridge
CB2 1TQ
United Kingdom
bollobas{at}msci.memphis.edu
Instituto de Matemática e Estatística
Universidade de São Paulo
Rua do Matão 1010
05508–090 Sáo Paulo, SP
Brazil
Department of Mathematics and Computer Science
Emory University
Atlanta, GA 30322
USA
rodl{at}mathcs.emory.edu
Institut für Informatik
Humboldt-Universität zu Berlin
Unter den Linden 6
D-10099 Berlin
Germany
schacht{at}informatik.hu-berlin.de
Zentrum Mathematik
Technische Universität München
Boltzmannstraße 3
D-85747 Garching bei München
Germany
taraz{at}ma.tum.de
Received 4 July 2006.
We consider edge colourings of the complete r-uniform hypergraph Kn(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 Kn(r) receives at most k different colours.
We investigate the threshold for k that guarantees that every (H, k)-local colouring of Kn(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 ‘sparse way’; 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 > 0 (the bound on the number of colours is allowed to depend on H and only); we think of such colourings n as ‘essentially finite’. 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 [‘Local edge colorings that are global’, J. Graph Theory 18 (1994) 389–399] and by the first two authors and Schelp [‘Essentially infinite colourings of graphs’, J. London Math. Soc. (2) 61 (2000) 658–670]. We also consider a related question for colourings of the integers and arithmetic progressions.
2000 Mathematics Subject Classification 05D10 (primary), 05C35 (secondary).
The first author was partially supported by NSF grants CCR 0225610 and DMS 0505550. The second author was partially supported by FAPESP and CNPq through a Temático–ProNEx project (Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6 and 479882/2004–5). The third author was partially supported by NSF grant DMS 0300529. The fourth author was partly supported by the DFG within the European graduate program ‘Combinatorics, Geometry, and Computation’ (No. GRK 588/2) and by DFG grant SCHA 1263/1–1. This work was supported in part by a CAPES/DAAD collaboration grant.