# Higher-dimensional Sierpiński partitions

Given a well-ordering of $$\mathbb{R}$$, there is a natural way to define an associated partition of pairs of real numbers into two pieces: one assigns the value $$0$$ to a pair $$r if the well-ordering agrees with the standard ordering on the pair, and gives it the value $$1$$ if not.

This construction is due originally to Sierpiński, and it is an important example/counterexample in Ramsey Theory because this coloring cannot have an uncountable homogeneous set: the separability of $$\mathbb{R}$$ tells us there must be a rational number between any two consecutive elements of a well-ordered (or reverse well-ordered) subset of $$\mathbb{R}$$.

In the square-bracket notation (discussed in my last question), Sierpiński's result says $$2^{\aleph_0}\nrightarrow [\aleph_1]^2_2.$$

Now Galvin and Shelah state the following in their paper 

We remark that an easy generalization of Sierpiński's proof shows that $$2^{\aleph_0}\nrightarrow [\aleph_1]^r_{r!(r-1)!}$$ for every positive integer r.

Their conclusion says that one can color the increasing $$r$$-tuples of reals with $$r!(r-1)!$$ colors in such a way that for any uncountable $$X\subseteq\mathbb{R}$$ each of these colors is realized by some $$r$$-tuple drawn from $$X$$.

I was unsuccessful at verifying their claim, as the most straightforward (to my mind) generalization of Sierpiński's proof provides a weaker coloring of $$r$$-tuples using $$r!$$-colors: one takes a well-ordering $$<^*$$ of $$\mathbb{R}$$ and the coloring assigns to an $$r$$-tuple $$a_0<\dots (in the usual ordering) the permutation of the index set $$r$$ that arises in the natural way once you rewrite your $$r$$-tuple in $$<^*$$-increasing order. Once again, the separability of finite powers of $$\mathbb{R}$$ is what allows you to conclude that every color appears on every uncountable set. So, this argument establishes only $$2^{\aleph_0}\nrightarrow [\aleph_1]^r_{r!}$$ and my question is how does one improve to obtain the stronger result mentioned by Galvin and Shelah?

It is not out of the question that there is a typo in their paper, but I am also aware that their definition of ''easy generalization'' is probably not the same as my own.

 Galvin, Fred; Shelah, Saharon, Some counterexamples in the partition calculus, J. Comb. Theory, Ser. A 15, 167-174 (1973). ZBL0267.04006.

• Alternatively, instead of ordering the intervals $(a_i,a_{i+1})$ by length, you could order them in the order that the rational numbers (in some fixed enumeration) land in them, I think that would work too.
– bof
Aug 23, 2022 at 6:51
• @bof Yes, there's a general preference to use at least a top-level tag for every paper. The standard parent tag for set theory is lo.logic, but here gn.general-topology might be suitable too, or even co.combinatorics — the question would be: where in arXiv would a paper in this topic be most likely to be posted? This seems totally unrelated to analysis (and anyway real-analysis is not top-level). At this point I believe that lo.logic is suitable and covers such a question (but not necessarily every question about infinite sets!).
– YCor
Aug 23, 2022 at 10:23
• @bof Yes, this works! Thank you! I will try to write up a self-answer to get this documented. Aug 23, 2022 at 14:26

We may assume $$r\ge3$$. Let $$\prec$$ be a well-ordering of $$\mathbb R$$. For $$n\in\mathbb N$$ let $$S_n$$ denote the set of all permutations of the set $$[n]=\{1,2,\dots,n\}$$.
Consider a set $$X=\{x_1,\dots,x_r\}\in\binom{\mathbb R}r$$ with $$x_1\lt x_2\lt\cdots\lt x_r$$ and let $$d_i=|x_i-x_{i+1}|$$ for $$1\le i\le r-1$$. Put $$X$$ in the class $$C_\sigma$$ ($$\sigma\in S_r$$) if $$x_{\sigma(1)}\prec x_{\sigma(2)}\prec\cdots\prec x_{\sigma(r)}$$, and put $$X$$ in the class $$D_\tau$$ ($$\tau\in S_{r-1}$$) if $$d_{\tau(1)}\gt d_{\tau(2)}\gt\cdots\gt d_{\tau(r-1)}$$. We have defined $$r!(r-1)!$$ disjoint classes $$C_\sigma\cap D_\tau$$ ($$\sigma\in S_r$$, $$\tau\in S_{r-1}$$). I claim that every uncountable subset of $$\mathbb R$$ contains members of each of these classes.
Let $$A$$ be an uncountable subset of $$\mathbb R$$. We may assume that $$A$$ has order type $$\omega_1$$ in the well-ordering $$\prec$$, and that $$U\cap A$$ is uncountable whenever $$U$$ is open and $$U\cap A\ne\varnothing$$.
We recursively choose $$r$$ distinct points in $$A$$. The first two points are chosen arbitrarily. Now suppose $$n$$ points have been chosen, $$2\le n\le r-1$$. We designate one of the previously chosen points as a target, and the next point we choose is unequal to but very close to the target; say, at a distance less that $$1/4$$ of the minimum distance between any two previously chosen points. Let $$X=\{x_1,\dots,x_r\}$$ be the set of points chosen in this way, $$x_1\lt x_2\lt\cdots\lt x_r$$; the indices do not, of course, represent the order in which the points were chosen.
It is easy to see that, by picking our targets appropriately, the set $$X$$ constructed in this way can be made to belong to any given class $$D_\tau$$. E.g., if the first two points are $$a\lt b$$, the third point will be chosen close to $$a$$ if $$\tau(2)\lt\tau(1)$$, close to $$b$$ if $$\tau(1)\lt\tau(2)$$.
Next, for each $$i\in[r]$$ choose a very small neighborhood $$U_i$$ of $$x_i$$. Since $$U_i\cap A$$ is uncountable, we can successively choose $$y_{\sigma(1)}\in U_{\sigma(1)}\cap A$$, $$y_{\sigma(2)}\in U_{\sigma(2)}\cap A$$, etc., so that $$y_{\sigma(1)}\prec y_{\sigma(2)}\prec\cdots\prec y_{\sigma(r)}$$. Thus the set $$Y=\{y_1,\dots,y_r\}\in\binom{\mathbb R}r$$ belongs to $$C_\sigma$$; moreover, it still belongs to $$D_\tau$$ if the neighborhoods $$U_i$$ were chosen small enough.