Polychromatic colorings

These are lectures notes of two talks Dani Livne gave in our Infinite Combinatorics seminar. I did not take notes in real-time, hence, all possible mistakes here are due to myself.

Recall that a function $f:A\rightarrow B$ is said to be $\theta$-to-1 if for every $b\in B$, the preimage $f^{-1}\{b\}$ has size $\theta$. It is said to be $\theta$-bounded iff $f^{-1}\{b\}$ has size $\le\theta$ for all $b\in B$.

Recall also that $\kappa\rightarrow(\lambda)^\delta_{\theta}$ stands for the assertion that for every function $f:[\kappa]^\delta\rightarrow\theta$, there exists some $H\subseteq\kappa$ of order-type $\lambda$ such that $H$ is monochromatic for $f$, that is, $f\restriction[H]^\delta$ is constant. Next, we deal with another extreme: $\kappa\rightarrow^{poly}(\lambda)^\delta_{\theta-\text{bounded}}$ asserts that for every $\theta$-bounded function $f:[\kappa]^2\rightarrow\kappa$, there exists some subset $R\subseteq\kappa$ of type $\lambda$ such that $R$ is rainbow for $f$, that is, $f\restriction[R]^\delta$ is injective.

The relation between the above two concepts is as follows.

Proposition (Galvin). $\kappa\rightarrow(\lambda)^\delta_{\theta}$ entails $\kappa\rightarrow^{poly}(\lambda)^\delta_{\theta-\text{bounded}}$.
Proof. Suppose that $f:[\kappa]^\delta\rightarrow\kappa$ is $\theta$-bounded. For every $\gamma<\kappa$, let $g_\gamma:\theta\rightarrow f^{-1}\{\gamma\}$ be a surjection. Finally, define $h:[\kappa]^\delta\rightarrow\theta$ by stipulating:$$h(\bar v)=\min\{ i<\theta\mid g_{f(\bar v)}(i)=\bar v\}.$$ Let $H\subseteq\kappa$ be homogeneous for $h$ of type $\lambda$. That is, $f\restriction [H]^\delta$ is constant, with value, say $i^*$. We claim that $H$ is rainbow for $f$. Indeed, if $\bar v,\bar u \in[H]^\delta$ are such that $f(\bar v)=f(\bar u)$, say it is equal to $\gamma$. Then $g_\gamma(i^*)=\bar v$ and $g_\gamma(i^*)=\bar u$, which is a contradiction. $\square$

So, it follows from Ramsey’s theorem $\omega\rightarrow(\omega)^2_2$ that $\omega\rightarrow^{poly}(\omega)^2_{2-\text{bounded}}$ holds. As Sierpinski showed that $\omega_1\rightarrow(\omega_1)^2_2$ fails, the study of $\omega_1\rightarrow^{poly}(\omega_1)^2_{2-\text{bounded}}$ becomes of interest.

Todorcevic proved that $\omega_1\rightarrow^{poly}(\omega_1)^2_{2-\text{bounded}}$ follows from PFA. Here, we shall verify the consistency of the converse.

Theorem (Galvin, private letters to Todorcevic. The proof has appeared in Abraham-Cummings-Smyth, 2007). The Continuum Hypothesis entails a function $f:[\omega_1]^2\rightarrow[\omega_1]^2$ such that:

1. $f$ is 2-to-1;
2. $f\restriction[A]^2$ is not 1-to-1 for any uncountable $A\subseteq\omega_1$.

Proof. The proof is a variation of an argument of Erdos-Hajnal-Milner. In particular, the consequence of CH that we shall utilize, is the existence of a sequence $\langle A_\delta\mid \delta<\omega_1\rangle$ of infinite bounded subsets of $\omega_1$ with the property that for every unbounded subset $A$ of $\omega_1$, there exists some $\delta<\omega_1$ such that $A_\delta\subseteq A$ (the so-called stick principle).

To start with, pick an arbitrary $g:[\omega]^2\rightarrow[\omega]^2$ which is 2-to-1. Then let $f\restriction[\omega]^2$ coincide with $g$. Next, fix an infinite ordinal $\beta<\omega_1$, and let us define $f\restriction(\beta\times\{\beta\})$. Let $\{ X^\beta_n\mid n<\omega\}$ be some (not necessarily injective) enumeration of $\{ A_\delta\mid \delta<\beta, A_\delta\subseteq\beta\}\cup\{\beta\}$. Since $X^\beta_n$ is infinite for all $n<\omega$, it is easy to recursively define a function $\varphi_\beta:\omega\rightarrow[\beta]^3$ with the properties:

1. $\varphi_\beta(n)\cap \varphi_\beta(m)=\emptyset$ for all $n<m<\omega$;
2. $\varphi_\beta(n)\subseteq X^\beta_n$ for all $n<\omega$.

Define $\varphi_\beta’:\omega\rightarrow[\beta]^2$ by letting $\varphi’_\beta(n):=\varphi_\beta(n)\setminus\{\max\varphi_\beta(n)\}$ for all $n<\omega$. Since $\beta\setminus\bigcup\varphi_\beta'[\omega]$ is infinite, it is now easy to pick a function $\psi_\beta:\omega\rightarrow[\beta]^2$ such that:

1. $\psi_\beta(n)\cap \psi_\beta(m)=\emptyset$ for all $n<m<\omega$;
2. $\bigcup\psi_\beta[\omega]=\beta\setminus\bigcup\varphi_\beta'[\omega]$.

Write $\mathcal P_\beta:=\varphi’_\beta[\omega]\cup\psi_\beta[\omega]$. Then $\mathcal P_\beta$ is a partition of $\beta$ into cells of size $2$. Thus, given $\alpha<\beta$, we find the unique cell $c\in\mathcal P_\beta$ such that $\alpha\in c$, and let $f(\alpha,\beta):=(\min(c),\beta)$. This completes the definition of $f$. Evidently, $f$ is indeed 2-to-1.

Finally, suppose that $A$ is an uncountable subset of $\omega_1$. Fix $\delta<\omega_1$ such that $A_\delta\subseteq A$. Fix a large enough $\beta\in A$ such that $\beta>\delta$ and $A_\delta\subseteq\beta$. Let $n<\omega$ be such that $A_\delta=X^\beta_n$. Let $\alpha<\gamma<\beta$ be such that $\varphi’_\beta(n)=\{\alpha,\gamma\}$. Then $\{\alpha,\gamma,\beta\}\subseteq A$ and $f(\alpha,\beta)=(\alpha,\beta)=f(\gamma,\beta)$. So $f\restriction[A]^2$ is not injective. $\square$

Our next goal is to establish the failure of $\kappa\rightarrow^{poly}(\omega)^\omega_{2-\text{bounded}}$ for every infinite cardinal $\kappa$. We commence with a couple of lemmas.

Lemma 1. There exist injections $f:[\omega]^\omega\rightarrow[\omega]^\omega, g:[\omega]^\omega\rightarrow[\omega]^\omega$ such that:

1. $f(x),g(x)$ are a proper subset of $x$, for all $x\in[\omega]^\omega$;
2. $\text{rng}(f)\cap\text{rng}(g)=\emptyset$.

Proof. Let $\prec$ be some well-ordering of $[\omega]^\omega$ in order-type $2^{\aleph_0}$. Define $f(x),g(x)$ by recursion. Given $x\in[\omega]^\omega$ such that $f(y),g(y)$ are defined for all $y\prec x$, let:

• $f(x):=\min_{\prec}(\{ z\in[x]^\omega\mid z\neq x\}\setminus\{ f(y),g(y)\mid y\prec x\})$;
• $g(x):=\min_{\prec}(\{ z\in[x]^\omega\mid z\neq x\}\setminus(\{ f(y),g(y)\mid y\prec x\}\cup\{f(x)\}))$.

Note that the definition is good since $|[x]^\omega|>|\{y\in[\omega]^\omega\mid y\prec x\}|+1$ for all $x\in[\omega]^\omega$. $\square$

Lemma 2. For every infinite cardinal $\kappa$, there exist injections $f:[\kappa]^\omega\rightarrow[\kappa]^\omega, g:[\kappa]^\omega\rightarrow[\kappa]^\omega$ such that:

1. $f(x),g(x)$ are a proper subset of $x$, for all $x\in[\kappa]^\omega$;
2. $\text{rng}(f)\cap\text{rng}(g)=\emptyset$.

Proof. Let $\{ a_\alpha\mid \alpha<\lambda\}$ be some maximal almost-disjoint (MAD) family in $[\kappa]^\omega$. That is:

• $a_\alpha\in[\kappa]^\omega$ for all $\alpha<\lambda$;
• $a_\alpha\cap a_\beta$ is finite for all $\alpha<\beta<\lambda$;
• for every $x\in[\kappa]^\omega$, there exists some $\alpha<\lambda$ such that $x\cap a_\alpha$ is infinite.

Of course, the existence of such a family is a consequence of Zorn’s lemma (i.e., of the axiom of choice). Recalling the previous lemma, we then fix for every $\alpha<\lambda$, injections $f_\alpha:[a_\alpha]^\omega\rightarrow[a_\alpha]^\omega, g_\alpha:[a_\alpha]^\omega\rightarrow[a_\alpha]^\omega$ such that:

1. $f_\alpha(x),g_\alpha(x)$ are a proper subset of $x$, for all $x\in[a_\alpha]^\omega$;
2. $\text{rng}(f_\alpha)\cap\text{rng}(g_\alpha)=\emptyset$.

Then, for all $x\in[\kappa]^\omega$, we let $\alpha_x$ be the least $\alpha<\lambda$ such that $x\cap a_\alpha$ is infinite, and put

• $f(x):=f_{\alpha_x}(x\cap a_{\alpha_x})\uplus(x\setminus a_{\alpha_x})$;
• $g(x):=g_{\alpha_x}(x\cap a_{\alpha_x})\uplus(x\setminus a_{\alpha_x})$.

We now verify that $f,g$ are injections, and that $\text{rng}(f),\text{rng}(g)$ are disjoint. For this fix $x,y\in[\kappa]^\omega$, $h\in\{f,g\}$, and suppose that $f(x)=h(y)$.

$\blacktriangleright$ If $\alpha_x=\alpha_y=\alpha^*$, then by $f(x)=h(y)$, we get in particular that $f_{\alpha^*}(x\cap a_{\alpha^*})=h_{\alpha^*}(y\cap a_{\alpha^*})$, and hence $h=f$ (since $g_{\alpha^*},f_{\alpha^*}$ have disjoint ranges), which in turn implies that $x\cap a_{\alpha^*}=y\cap a_{\alpha^*}$ (since $f_{\alpha^*}$ is injective). Recalling that $f(x)=f(y)$ entails also that $x\setminus a_{\alpha^*}=y\setminus a_{\alpha^*}$, we conclude that $x=y$.

$\blacktriangleright$ If $\alpha_x<\alpha_y$, then $a_{\alpha_x}\cap a_{\alpha_y}$ is finite, and in particular $f_{\alpha_x}(x\cap a_{\alpha_x})\cap h_{\alpha_y}(y\cap a_{\alpha_y})$ is finite. So, from $f(x)=h(y)$, we infer the existence of a finite set $F$, such that $f_{\alpha_x}(x\cap a_{\alpha_x})\setminus F\subseteq (y\setminus a_{\alpha_y})$. In particular, $a_{\alpha_x}\cap y$ is infinite, contradicting the minimality of $\alpha_y$. So this case is void. $\square$

Theorem (Palumbo-Tserunyan, 2012). $\kappa\rightarrow^{poly}(\omega)^\omega_{2-\text{bounded}}$ fails for every infinite cardinal $\kappa$.
Proof. Let $f,g$ be as in Lemma 2. Define $c:[\kappa]^\omega\rightarrow[\kappa]^\omega\times 2$ as follows. Given $x\in[\kappa]^\omega$. If there exists $y\in[\kappa]^\omega$ such that $f(y)=x$, then $y$ is unique, and we let $c(x):=(y,0)$. If there exists $y\in[\kappa]^\omega$ such that $g(y)=x$, then $y$ is again unique, and we let $c(x):=(y,0)$. If $x\not\in(\text{rng}(f)\cup\text{rng}(g))$, then let $c(x):=(x,1)$. Since $f,g$ are injectives, we get that $c$ is $2$-bounded (actually, we could have been slightly more careful and insure that $c$ is strictly 2-to-1). Finally, to see that $c$ admits no infinite rainbow set, fix an arbitrary $x\in[\kappa]^\omega$. Then, we have:

• $\{f(x),g(x)\}\subseteq [x]^\omega$;
• $c(f(x))=(x,0)=c(g(x))$.

So, $c\restriction[x]^\omega$ is not 1-to-1. $\square$