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}}$,''}$

but

$V^{{\mathcal{Q}}}\models\text{`` ${\omega _{1}}$ is the union of countably many $f$-rainbow sets. ''}$

back