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


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<i(\alpha)}A_{\alpha, i}\in F. 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\})<i. 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s