The Square Bracket Partition Relation

I wanted to use this post to briefly talk about the square bracket partition relation, as a lot of the work I’ve been doing recently has centered around a very particular instance of this.

Definition: Suppose $\kappa$, $\mu$, and $\lambda$ are cardinals, and that $\gamma$ is an ordinal. The symbol

$\kappa\to[\mu]^\lambda_\gamma$

means that, for any coloring $F: [\kappa]^\lambda\to\gamma$ of the cardinality $\lambda$ subsets of $\kappa$ in $\gamma$ colors, there is some $H\subseteq[\kappa]^\mu$ such that $ran(F\upharpoonright [H]^\lambda)\subsetneq\gamma$. We say that $H$ is weakly homogeneous in this case.

Perhaps the best way to get a handle on the square bracket partition relation is to look a colorings of pairs. In particular, one question that appears in the literature is, given a cardinal $\lambda$, when does the relation $\lambda\to[\lambda]^2_\lambda$ hold? In order for this to fail, there has to be a coloring $F:[\lambda]^2\to\lambda$ such that, for any $H\subseteq \lambda$ with $|H|=\lambda$, we have that $ran(F\upharpoonright [H]^2)=\lambda$. That is, there is a coloring of the pairs of $\lambda$ which is so pathological, that restricting it to any subset of size $\lambda$ gives us a coloring which hits every color.

We can see the failure of this partition relation as a gross failure of Ramsey’s theorem for $\lambda$. So with that in mind, I’m going to focus on colorings of pairs in this post, as there is a very deep theory that comes from asking to construct pathological colorings of pairs.

For example, Todorčević was able to show that, for regular uncountable $\kappa$, we have $\kappa^+\not\to[\kappa^+]^2_{\kappa^+}$ using his walks on ordinals technique. Shelah was then able to further expand upon this to show that if $\lambda$ has a non-reflecting stationary subset, then $\lambda\not\to[\lambda]^2_\lambda$. In more recent work, both Shelah and Eisworth have been able to show that this, and an even stronger negative partition relation hold for many $\lambda=\mu^+$ where $\mu$ is singular by combining the machinery of scales and club guessing with walks on ordinals.

I’ll probably return to that stuff in a later post. In particular, I want to give an overview of what’s known in the area, and motivate some of the open questions. I’ve been spending most of my time looking at colorings of all finite subsets of $\lambda$, but in that case one can actually work with elementary submodels instead. Lately, however, I’ve been interested in colorings of pairs, so posting about this will be a nice way of keeping myself on track. First though, I want to talk about a case when the square bracket partition relation does hold.

Theorem (Prikry): If $\mathfrak{c}=2^{\aleph_0}$ is real-valued measurable, then $\mathfrak{c}\to[\aleph_1]^2_{\mathfrak{c}}$.

Proof: Much like how we exploit the $\kappa$-complete, normal measure on a measurable $\kappa$ to show that $\kappa$ is Ramsey, we will use the ideal of null sets to find a weakly homogeneous set for any coloring.

So let $\mu$ be a $\mathfrak{c}$-additive, atomless measure on $\mathfrak{c}$ with measure algebra all of $\mathcal{P}(\mathfrak{c})$. Let $I=\{A\subseteq \mathfrak{c} : \mu(A)=0\}$ be the ideal of $\mu$-null sets, and let $F$ denote the dual filter. It’s relatively easy to see that $I$ must be $\mathfrak{c}$-complete and $\aleph_1$-saturated.

Now, fix a coloring $c:[\mathfrak{c}]^2\to\aleph_1$. For each $\alpha<\mathfrak{c}$ and $i<\omega_1$, let

$A_{\alpha, i}=\{\beta\in(\alpha,\mathfrak{c}) : c(\{\alpha,\beta\})=i \}$.

Note that for each $\alpha<\mathfrak{c}$, we have that $\bigcup_{i<\omega_1}A_{\alpha,i}=\mathfrak{c}\setminus \alpha\in F$. So by completeness and saturation of $I$, we have that there is some $i_\alpha<\omega_1$ such that $A_\alpha=\bigcup_{i. Now we recursively build an increasing sequence $\{\alpha_\xi : \xi<\mathfrak{c}\}$ with the property that $\alpha_\xi\in \bigcup_{\eta<\xi}A_{\alpha_eta}$. This is easy by the $\mathfrak{c}$-completeness of $F$.

Now, note that since real-valued measurability of $\mathfrak{c}$ gives us that $\mathfrak{c}>\aleph_1$, we can find a set of $\xi$ of size $\mathfrak{c}$ such that $i(\alpha_\xi)=i$ for each such $\xi$. So reindex and let $H=\{\alpha_\xi : \xi<\mathfrak{c}\}$ be the set of corresponding $\alpha_\xi$. Then we have that $\alpha_\xi\in H$ gives us that $\alpha_\xi\in\bigcup_{\eta<\xi}A_{\alpha_\eta}$ and so $c(\{\alpha_\eta,\alpha_\xi\}). But the we’re done, as $c\upharpoonright [H]^2\subseteq i\subsetneq\omega_1$.

It should be noted that the failure of CH was necessary here by Todorčević’s theorem.