Logic Colloquium 2008

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

Given a function f:[X]^{n}\to X a subset Y of X is a rainbow subset for f provided f\restriction[Y]^{n} is one-to-one. A typical question is the following old problem of Erdős: Assume that the colouring f:[{\omega}_{1}]^{2}\to 3 establishes the negative partition relation {\omega}_{1}{\not\makebox[-7pt]{}\rightarrow}[{\omega}_{1}]^{2}_{3}. Is there a rainbow triangle for f?

We survey some old and new results and we also present some new theorems. E.g we show that if a colouring c establishes {\omega _{2}}{\not\makebox[-7pt]{}\rightarrow}[({\omega _{1}};{\omega})]^{2}_{{\omega}} then c establishes this negative partition relation in each Cohen-generic extension of the ground model, i.e. this property of c 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 c:[{\omega _{2}}]^{2}\to 2 establishing {\omega _{2}}{\not\makebox[-7pt]{}\rightarrow}[({\omega _{1}};{\omega})]^{2}_{2} such that some colouring g:[{\omega _{1}}]^{2}\to 2 can not be embedded into c.

It is also consistent that 2^{{{\omega _{1}}}} is arbitrarily large, and there is a function g establishing 2^{{{\omega _{1}}}}{\not\makebox[-7pt]{}\rightarrow}[({\omega _{1}},{\omega _{2}})]^{2}_{{{\omega _{1}}}} but there is no uncountable g-rainbow subset of 2^{{{\omega _{1}}}}.

We also show that if GCH holds then for each k\in{\omega} there is a k-bounded colouring f:[{\omega _{1}}]^{2}\rightarrow{\omega _{1}} and there are two c.c.c posets \mathcal{P} and \mathcal{Q} such that

V^{{\mathcal{P}}}\models\text{``$f$ c.c.c-indestructibly establishes
${\omega _{1}}{\not\makebox[-7pt]{}\rightarrow}^{*}[({\omega _{1}};{\omega _{1}})]_{{k-bdd}}$,''}


${\omega _{1}}$ is the union of countably many
$f$-rainbow sets.