2
$\begingroup$

This seems likely to be an instance of general combinatorial theorem. But which one?

Definition 1:

  1. Define an order-theoretic tree $T$ to be a poset such that for any node, the set of elements less than that node is well-ordered.
  2. The size of $T$ is the cardinality of the set of nodes in $T$.
  3. For two nodes $n_1\neq n_2\in T$, if $n_1< n_2$ and $n_1$ is greatest strictly less than $n_2$ (and equivalently, $n_2$ is least greater than $n_1$), then call $n_1$ the parent of $n_2$ (uniqueness is by condition 1 above) and $n_2$ a child of $n_1$.

All trees are order-theoretic henceforth. If we write "order-theoretic tree", this is just for emphasis.

Definition 2: Suppose $\beta$ is a cardinal. Then say a tree $T$ is $\beta$-branching when every node in $T$ has strictly fewer than $\beta$ children.
(For example, an $\omega$-branching tree is what would normally be called finitely branching.)

Definition 3: Suppose $C$ is a set. A $C$-colouring on a tree $T$ is an assignment of an element $c\in C$ to each node $n$ of $T$.

Fix the following data:

  • A pair of cardinals $\alpha<\beta$ where $\alpha$ is uncountable. (Note that we are free to take $\beta$ much larger than $\alpha$.)
  • A set of colours $C$ of cardinality $\alpha$.
  • A $\beta$-branching order-theoretic tree $T$ of size $\beta$.

So intuitively, writing "large" for $\beta$, "small" for "less than $\beta$", and "very small" for $\alpha$: $T$ is "large", local branches are "small", and available colours are "very small".

Lemma 1 (required to prove): There exists some colour $c\in C$ and some node $n\in T$ such that any path $p$ in $T$ starting from $n$ is either shorter than $\beta$ or has length $\beta$ and encounters $\beta$ many nodes of colour $c$.

To sum up intuitively:

If a large order-theoretic tree has small branches and a very small number of colours, then there exists a large subtree and a colour $c$ such that any large path in the subtree has a large number of $c$-coloured nodes.

Example: Consider a large tree such that one path from the root is coloured red, and the rest of the tree is coloured blue. Then take $n$ to be any blue node in $T$.

I wonder if Lemma 1 is a standard result, or is easily proved from standard results?

$\endgroup$
7
  • $\begingroup$ Thank you very much @bof for your comments. I have edited the question to be more precise. Thank you. $\endgroup$
    – Jim
    Commented Mar 28, 2021 at 12:29
  • $\begingroup$ The statement that $T$ is $\beta$-branching does not mean that the branches of $T$ (i.e., paths through $T$ starting at the root) have cardinality less than $\beta$: it means that each node of $T$ has degree less than $\beta$ or, equivalently, that it has fewer than $\beta$ immediate successors in the natural tree order. $\endgroup$ Commented Mar 28, 2021 at 22:32
  • $\begingroup$ Thank you @BrianM.Scott Edited to correct this. (I avoided "node has cardinality less than $\beta$" because this would include the edge running back up to a parent node, which in the case of e.g. $\beta=2$ would matter.) I hope the reformulation is both precise and elementary $\endgroup$
    – Jim
    Commented Mar 29, 2021 at 4:16
  • $\begingroup$ Since you’re dealing only with $\beta\ge\omega_2$, that’s not a real problem. And what you have isn’t quite right, since it’s not clear that you’re talking only about subtrees whose roots are immediate successors of the node. (As long as the subtree rooted at the node in question has size $\beta$, that node in some sense leads to $\beta$ subtrees.) If you want to avoid the degree problem that arises with $\beta<\omega$, I still think that it’s best simply to say that each node has fewer than $\beta$ immediate successors. $\endgroup$ Commented Mar 29, 2021 at 4:27
  • $\begingroup$ And the change that you just now made is just fine, too. $\endgroup$ Commented Mar 29, 2021 at 4:28

1 Answer 1

0
$\begingroup$

Lemma 1 is false. Take $\beta$ to be any limit ordinal and colours to be $C=\{0,1\}$. Let nodes of the tree be functions $n:\alpha\to\{0,1\}$ for any $\alpha<\beta$ ($\alpha$ in this answer has nothing to do with the $\alpha$ in the question).

Define the colouring $f$ by: $$ \begin{array}{r@{\ }l@{\qquad}l} f(\alpha)=&c & \text{if }\exists c{\in}C.\exists \alpha'{<}\alpha.\forall \alpha'\leq\alpha''{<}\alpha.n(\alpha'')=c \\ f(\alpha)=&0 & \text{otherwise} \end{array} $$

Unpacking this in plain English:

  • The root node $n:0\to\{0,1\}$ is coloured with $0$.
  • A non-limit node is coloured with its last element --- so if $n:\alpha{+}1\to\{0,1\}$ then $f(n)=n(\alpha)$.
  • A limit node tended to by ones, is coloured with $1$.
  • A limit node not tended to by ones, is coloured with $0$.

Then any node sees a branch coloured all with $0$s, and a branch coloured all with $1$s.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .