3
$\begingroup$

Consider the full $m$-ary tree of height $k$ with root node $\emptyset$. Branches in this tree can be considered as functions $f:k\rightarrow m$ and nodes of the tree as total functions $\hat{f}:k'\rightarrow m$ ordered by extension (where $k'\leq k$).

Define a coloring $\mathcal{C}$ of the nodes in the tree inductively:

  1. Pick a (surjective) three-coloring $c:m\rightarrow\{1, 3, 4\}$; this will color every node in the tree. Let $\mathcal{C}$ agree with $c$ on the first non-empty level of the tree (level 1).

  2. At stage $n+1\leq k$, color the nodes in level $n+1$ of the tree (nodes of the form $\hat{f}(n+1)$) by setting $\mathcal{C}(\hat{f}(n+1))=\mathcal{C}(\hat{f}(n))\cdot c(\hat{f}(n+1))\mod 6$.

The intuitive idea here is that 1 is a "good" color (say white), 3 and 4 are non-neutral colors (say red and blue) and 0 is a "bad" color (say black). The inductive step "mixes" colors by "painting over" the original color of the node given by $c$ using the color of the node immediately preceding it. Given a node at stage $n+1$, let's call it $p$, $\mathcal{C}$ will re-color $p$ as follows:

a. If the node immediately preceding $p$ is colored white, leave $p$ the same color it was given by $c$. [This is because $\delta\cdot 1=\delta\mod 6$ for all $\delta\in\{1, 3, 4\}$]

b. If the node immediately preceding $p$ is colored black, color $p$ black.[This is because $\delta\cdot 0=0\mod 6$ for all $\delta\in\{0, 1, 3, 4\}$.]

c. If the node immediately preceding $p$ is colored red, color $p$ red if it was originally colored red or white by $c$, color $p$ black if it was originally colored blue by $c$. [This is because $\delta\cdot 3=3\mod 6$ for all $\delta\in\{1, 3,\}$, and $4\cdot 3=0\mod 6$.]

d. If the node immediately preceding $p$ is colored blue, color $p$ blue if it was originally colored blue or white by $c$, color $p$ black if it was originally colored red by $c$. [This is because $\delta\cdot 4=4\mod 6$ for all $\delta\in\{1, 4,\}$, and $3\cdot 4=0\mod 6$.]

Now consider a maximal antichain in the colored tree. We will ignore all nodes in this antichain that are colored either red or blue. Under what circumstances are the remaining nodes split even among white and black? It is relatively easy to find such maximal antichains, but all of the ones I've been able to construct are "skewed" in some way in the tree (i.e., they are not very nice, in a sense).

So (finally), I have the following Question: Can there be a maximal antichain $\mathcal{A}$ where all nodes are on the "same level", i.e. every element in $\mathcal{A}$ is of the form $\hat{f}(k')$ for some fixed $k'\leq k$, and such that the number of white nodes in $\mathcal{A}$ is equal to the number of black nodes in $\mathcal{A}$?

I do know at this point that there is always a minimum level of the colored tree where the number of black nodes at that level is strictly greater than the number of white nodes at that level. And this will be true for every higher level as well. So the question is: could the level immediately below this minimum level have the property I'm seeking.

I conjecture the answer is NO but so far can't establish this.

Edit: I should mention that I intend $k>2$ and the surjective condition for the initial coloring $c$ requires $m\geq 3$.

For clarification, note that the "original" color of a node only depends on whether it is the first, second, etc. child of the parent node not its position in the tree.

There are $m^n$ nodes at level $n$ of the tree. If we let $W$ be the number of white nodes at level 1, then there will be $W^n$ nodes at level $n$.

There will never be a Black node at level 1. They start appearing at level 2 and from then on, they grow at an enormous rate; much faster than the white nodes but not as fast as $m^n.$

I have an exact calculation for the black nodes at level n; this depends on the number of blue and red nodes at level 1 (and this is unavoidable).

$\endgroup$

1 Answer 1

3
$\begingroup$

The recolouring scheme can be described as follows. The colours correspond to the elements of the poset of subsets of $\{1,2\}$ ordered by inclusion, with white at the bottom and black at the top. The final colour $\mathcal C(v)$ of a vertex is the supremum of the colours of its ancestors. The number of white and black vertices on each level can then be calculated explicitly using inclusion-exclusion.

Let $w$, $r$ and $b$ be the number of initially white, red and blue children of each vertex. The number of white vertices on level $n$ is $w^n$, and the number of black vertices is $(w+r+b)^n - (w+r)^n - (w+b)^n + w^n$ (We want to count the number of paths using at least one blue and at least one red, so we take the total number of paths, subtract the number of paths missing red and the number missing blue, then add back the number missing both.) For the number of black and white vertices on the $n$th level to agree we want $(w+b+r)^n = (w+b)^n + (w+r)^n$. For $n=2$ this simplifies to $2rb = w^2$, so the second level has equal numbers of black and white vertices if $w=r=2$ and $b=1$.

Edit: Everett Piper points out below that, for $n > 3$, there are no solutions by Fermat's Last Theorem. So $2rb=w^2$ characterises the colourings for which some level is good precisely.


I'm preserving the original answer below the line so that the comment history makes sense.

Is this a construction that produces half white and half black on the level with 4 vertices?

$\endgroup$
5
  • $\begingroup$ Well, the coloring construction requires 3 nodes at the first level and I intended the tree to grow upward. Ignoring this, there would be a copy of the first level (white and blue) after the white node. Since these are the only colors in your tree, the two nodes after the blue node would both be blue. Thus your bottom level would be colored from left-to-right as white, blue, blue, blue. So no, your level 2 antichain would not count. I should also mention that I intend $k$ to be at least 3. I'll edit. $\endgroup$ Nov 2, 2013 at 9:34
  • $\begingroup$ Let me also point out that black nodes only arise out of other black nodes or when a red node precedes a blue one (or vice versa) in the orginal coloring of the tree given by $c$. $\endgroup$ Nov 2, 2013 at 9:38
  • $\begingroup$ @EverettPiper, thank you for the clarification. Perhaps you could edit the OP to make explicit that in the initial colouring (determined by $c$) the colour only depends on whether you are the first, second, third etc. child of your parent, and not your position in the tree. (You do say this in the current version, but the reader has to correctly parse the $f(n)$ notation to get there.) $\endgroup$
    – Ben Barber
    Nov 2, 2013 at 9:49
  • 1
    $\begingroup$ this is a much cleaner formulation of the coloring scheme. Thank you! Except now it appears that the problem is equivalent to solving Fermat's Last Theorem: Let $z=w+r+b$, $x=w+b$, and $y=w+r$. Then the maximal antichain given by level $n$ has the same number of white nodes as black nodes if and only if $z^n=x^n+y^n$. Since this equation is false for $n$ larger than 2, no such antichain given by level $n$ for $n\geq 3$ can be balanced. $\endgroup$ Nov 2, 2013 at 11:42
  • $\begingroup$ Ah, well spotted! I'll edit your observation into the answer. Are you able to say anything about where this problem comes from? $\endgroup$
    – Ben Barber
    Nov 2, 2013 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.