Let us say a tree is a partially ordered set $(P, \leqslant )$ such that for any $t\in P$, the ancestor set $\{s\in P: s\leqslant t\}$ is finite and linearly ordered. We let $MAX(P)$ denote the set of $\leqslant$-maximal members in the tree $P$. It is assumed that every subset of a tree is ordered with the same order as the original tree, so that each subset of a tree is also a tree. Now we can define the derived tree $P'=P\setminus MAX(P)$. We can then define the transfinite derivatives $$P^0=P,$$ $$P^{\xi+1}=(P^\xi)',$$ and if $\xi$ is a limit ordinal, $$P^\xi=\bigcap_{\zeta<\xi}P^\zeta.$$ We say $P$ is well-founded if there exists an ordinal $\xi$ such that $P^\xi=\varnothing$. In this case, we let $\text{rank}(P)$ be the minimum $\xi$ such that $P^\xi=\varnothing$. We say a tree is ill-founded if it is not well-founded, but in this question we do not care about those.

Ramsey-type questions

For a tree $P$ and $n\in\mathbb{N}$, let $\langle P\rangle^p$ denote the set of linearly ordered subsets of $P$ with cardinality $p$. For an ordinal $\xi$, does there exist an (and if there does, what is the minimum such) ordinal $\zeta=\zeta(\xi, p, k)$ such that for any finite set $F$ with $|F|=k$, any tree $P$ with $\text{rank}(P)\geqslant \zeta$, and any function $f:\langle P\rangle^p\to F$, there exists $Q\subset P$ with $\text{rank}(Q)=\xi$ such that $f|_{\langle Q\rangle^p}$ is constant.

Quantified separation

The derivatives take away one "level" of leaves at a time. If $P$ is a tree with rank $\alpha \beta$, we can consider the subsets $(P^{\alpha \gamma}\setminus P^{\alpha(\gamma+1)})_{\gamma<\beta}$, which is a partition of $P$ into subtrees $P^{\alpha \gamma}\setminus P^{\alpha(\gamma+1)}$, each of which has rank exactly $\alpha$. We can also think of these subtrees as the level sets of the function $h_\alpha:P\to [0, \beta)$ given by $$h_\alpha(t)=\max\{\gamma: t\in P^{\alpha \gamma}\}.$$ We can then define the $\alpha$-separation $s_\alpha(s,t)$ of two nodes $s,t\in P$ by letting $s_\alpha(s,t)=0$ if $h_\alpha(s)=h_\alpha(t)$ (intuitively, they are not $\alpha$-separated) and $s_\alpha(s,t)=1$ if $h_\alpha(s)\neq h_\alpha(t)$ (intuitively, they are $\alpha$-separated).

Now if $P$ is a tree with rank $\alpha_0 \alpha_1\ldots \alpha_{n-1}$ $(n>0)$, then for each $0\leqslant i<n$, we can apply the preceding construction with $$\alpha= \alpha_0 \alpha_1 \ldots \alpha_i$$ and $$\beta= \alpha_{i+1}\ldots \alpha_{n-1}.$$ Here, we adopt the covention in the $i=n-1$ case that the empty product $\alpha_n\ldots \alpha_{n-1}$ is $1$. Since $\alpha_0\ldots \alpha_{n-1}$ is the full rank of the tree, no two nodes can be $\alpha_0\ldots \alpha_{n-1}$-separated, so $s_{\alpha_0\ldots \alpha_{n-1}}(s,t)=0$ for all $s,t\in P$. Furthermore, the list $$s_{\alpha_0}(s,t), s_{\alpha_0\alpha_1}(s,t), s_{\alpha_0\alpha_1\alpha_2}(s,t), \ldots, s_{\alpha_0\alpha_1\ldots \alpha_{n-1}}(s,t)$$ is either a list of all $1$ or a list with several $0$s follows by $1$s, and the last term is $1$. We can then define $$\varsigma_P(s,t)=\min \{i\leqslant n: s_{\alpha_0\ldots \alpha_i}(s,t)=1\}.$$

Alternatively, we can think about viewing the tree $P$ at different resolutions. At the highest resolution, we can only see inner trees of the form $P^{\alpha_0 \gamma}\setminus P^{\alpha_0 (\gamma+1)}$, at the next resolution we can see trees of the form $P^{\alpha_0 \alpha_1 \gamma}\setminus P^{\alpha_0\alpha_1(\gamma+1)}$, etc. The lowest resolution is the full tree. Then $\varsigma_P(s,t)$ can be described as the lowest resolution which allows us to see both $s$ and $t$ at the same time.

One can show that, if the rank of $P$ is $\alpha_0\ldots \alpha_{n-1}$, where $\alpha_i=\omega^{\omega^{\varepsilon_i}}$ and $\varepsilon_0\geqslant \ldots \geqslant \varepsilon_{n-1}$, then for any finite set $F$ and any function $f: \langle P\rangle^2\to F$, we can find a subtree $Q$ of $P$ and a function $g:\{0, \ldots, n-1\}\to F$ such that $\varsigma_Q=\varsigma_P|_{\langle Q \rangle^2}$, the rank of $Q$ is equal to the rank of $P$, and $g(\varsigma_P(s,t))=f(\{s,t\})$ for all $\{s,t\}\in \langle Q\rangle^2$. That is, the colors received by pairs in $Q$ does not really depend on the pair, but only on their separation, and we can pass from $P$ to $Q$ without losing anything from the rank or disturbing the separation. This allows us to completely answer the Ramsey question above in the case $p=2$. The fixed points are exactly the ordinals which, when factored as above, have $n=1$. That is, ordinals consisting of a single factor $\omega^{\omega^\xi}$ (or the finite ordinals $0,1,2$, obviously). This result more or less not only solves the stabilization question, but provides a heuristic for knowing why these multiplicatively indecomposable ordinals are the ones which admit this stabilization result for pair coloring.

My question is how much light does this approach to the pair coloring shed on the problem of coloring triples, etc.? Does the preceding paragraph offer an obvious inductive hypothesis to answer the analogous question for coloring triples, 4-tuples, etc.? Or, does it provide us with a starting point to prove negative results? For example, if $P$ is a tree with rank $\alpha_0 \ldots \alpha_{n-1}$ as above, and if $\alpha_i=\omega^{\omega^{\varepsilon_i}}$ with $\varepsilon_0\geqslant \ldots \geqslant \varepsilon_{n-1}$, for $\{s,t,u\}\in \langle P\rangle^3$ with $s<t<u$, define $$ f(\{s,t,u\}) = \left\{ \begin{array}{lr} 1 & : \varsigma_P(s,t)<\varsigma_P(t,u)\\ 0 & : \varsigma_P(s,t)\geqslant \varsigma_P(t,u). \end{array} \right. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy