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\to 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 \to (\lambda {)}_{\theta }^{\delta }$ stands for the assertion that for every function $f:[\kappa {]}^{\delta }\to \theta$, there exists some $H\subseteq \kappa$ of order-type $\lambda$ such that $H$ is monochromatic for $f$, that is, $f\upharpoonright [H{]}^{\delta }$ is constant. Next, we deal with another extreme: $\kappa {\to }^{poly}(\lambda {)}_{\theta -\text{bounded}}^{\delta }$ asserts that for every $\theta$-bounded function $f:[\kappa {]}^2\to \kappa$, there exists some subset $R\subseteq \kappa$ of type $\lambda$ such that $R$ is rainbow for $f$, that is, $f\upharpoonright [R{]}^{\delta }$ is injective.

The relation between the above two concepts is as follows.

Proposition (Galvin). $\kappa \to (\lambda {)}_{\theta }^{\delta }$ entails $\kappa {\to }^{poly}(\lambda {)}_{\theta -\text{bounded}}^{\delta }$.
Proof. Suppose that $f:[\kappa {]}^{\delta }\to \kappa$ is $\theta$-bounded. For every $\gamma <\kappa$, let $g_{\gamma }:\theta \to f^{-1}\{\gamma \}$ be a surjection. Finally, define $h:[\kappa {]}^{\delta }\to \theta$ by stipulating:$$h(\overline{v})=min\{i<\theta \mid g_{f(\overline{v})}(i)=\overline{v}\}.$$ Let $H\subseteq \kappa$ be homogeneous for $h$ of type $\lambda$. That is, $f\upharpoonright [H{]}^{\delta }$ is constant, with value, say $i^{\ast }$. We claim that $H$ is rainbow for $f$. Indeed, if $\overline{v},\overline{u}\in [H{]}^{\delta }$ are such that $f(\overline{v})=f(\overline{u})$, say it is equal to $\gamma$. Then $g_{\gamma }(i^{\ast })=\overline{v}$ and $g_{\gamma }(i^{\ast })=\overline{u}$, which is a contradiction. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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

Todorcevic proved that ${\omega }_1{\to }^{poly}({\omega }_1{)}_{2-\text{bounded}}^2$ 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\to [{\omega }_1{]}^2$ such that:

1. $f$ is 2-to-1;
2. $f\upharpoonright [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 $⟨A_{\delta }\mid \delta <{\omega }_1⟩$ 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\to [\omega {]}^2$ which is 2-to-1. Then let $f\upharpoonright [\omega {]}^2$ coincide with $g$. Next, fix an infinite ordinal $\beta <{\omega }_1$, and let us define $f\upharpoonright (\beta \times \{\beta \})$. Let $\{X_n^{\beta }\mid n<\omega \}$ be some (not necessarily injective) enumeration of $\{A_{\delta }\mid \delta <\beta ,A_{\delta }\subseteq \beta \}\cup \{\beta \}$. Since $X_n^{\beta }$ is infinite for all $n<\omega$, it is easy to recursively define a function ${\phi }_{\beta }:\omega \to [\beta {]}^3$ with the properties:

1. ${\phi }_{\beta }(n)\cap {\phi }_{\beta }(m)=\mathrm{\varnothing }$ for all $n<m<\omega$;
2. ${\phi }_{\beta }(n)\subseteq X_n^{\beta }$ for all $n<\omega$.

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

1. ${\psi }_{\beta }(n)\cap {\psi }_{\beta }(m)=\mathrm{\varnothing }$ for all $n<m<\omega$;
2. $\bigcup {\psi }_{\beta }[\omega ]=\beta \setminus \bigcup {\phi }_{\beta }^{\prime }[\omega ]$.

Write ${\mathcal{P}}_{\beta }:={\phi }_{\beta }^{\prime }[\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_n^{\beta }$. Let $\alpha <\gamma <\beta$ be such that ${\phi }_{\beta }^{\prime }(n)=\{\alpha ,\gamma \}$. Then $\{\alpha ,\gamma ,\beta \}\subseteq A$ and $f(\alpha ,\beta )=(\alpha ,\beta )=f(\gamma ,\beta )$. So $f\upharpoonright [A{]}^2$ is not injective. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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

Lemma 1. There exist injections $f:[\omega {]}^{\omega }\to [\omega {]}^{\omega },g:[\omega {]}^{\omega }\to [\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)=\mathrm{\varnothing }$.

Proof. Let $\prec$ be some well-ordering of $[\omega {]}^{\omega }$ in order-type $2^{{\mathrm{\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):=\underset{\prec }{min}(\{z\in [x{]}^{\omega }\mid z\ne x\}\setminus \{f(y),g(y)\mid y\prec x\})$;
• $g(x):=\underset{\prec }{min}(\{z\in [x{]}^{\omega }\mid z\ne 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 }$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Lemma 2. For every infinite cardinal $\kappa$, there exist injections $f:[\kappa {]}^{\omega }\to [\kappa {]}^{\omega },g:[\kappa {]}^{\omega }\to [\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)=\mathrm{\varnothing }$.

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 }\to [a_{\alpha }{]}^{\omega },g_{\alpha }:[a_{\alpha }{]}^{\omega }\to [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 })=\mathrm{\varnothing }$.

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)$.

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

$▸$ 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. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Theorem (Palumbo-Tserunyan, 2012). $\kappa {\to }^{poly}(\omega {)}_{2-\text{bounded}}^{\omega }$ fails for every infinite cardinal $\kappa$.
Proof. Let $f,g$ be as in Lemma 2. Define $c:[\kappa {]}^{\omega }\to [\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\notin (\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\upharpoonright [x{]}^{\omega }$ is not 1-to-1. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$