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$

This entry was posted in Blog, Expository and tagged , . Bookmark the permalink.

2 Responses to Polychromatic colorings

  1. Literature says:

    The CH-result is due to Galvin (as well as its proof). It is mentioned in Todorcevic’s paper whose link you provide (page 43 lines 11-12). It is curious that you don’t mention the remark on page 43, line 13 of the same paper. Galvin’s original notation for this partition symbol is in my opinion much better as it points out the duality to the ordinary partition symbol.

    • saf says:

      Sorry about that. Indeed, in Todorcevic’s paper as well as in the Abraham-Cummings-Smyth paper, the CH result is attributed to Galvin.

      Thanks for the correction!

Leave a Reply

Your email address will not be published. Required fields are marked *