Logic Colloquium 2008

Rainbow ColouringsAlfréd Rényi Institute of Mathematics, Budapest, Reáltanoda utca 13–15, H-1053, Hungary soukup@renyi.hu

Given a function a subset of is a rainbow subset for provided is one-to-one. A typical question is the following old problem of Erdős: Assume that the colouring establishes the negative partition relation . Is there a rainbow triangle for ?

We survey some old and new results and we also present some new theorems. E.g we show that if a colouring establishes then establishes this negative partition relation in each Cohen-generic extension of the ground model, i.e. this property of is Cohen-indestructible. This result yields a negative answer to a question of Erdős and Hajnal: it is consistent that GCH holds and there is a colouring establishing such that some colouring can not be embedded into .

It is also consistent that is arbitrarily large, and there is a function establishing but there is no uncountable -rainbow subset of .

We also show that if GCH holds then for each there is a -bounded colouring and there are two c.c.c posets and such that

but

back