Rainbow Combinatorial Lines in Hypercubes

We will begin with the base case: n = 1. If n = 1, then we already know that $ah(k,1)=k$ implies $ah(2,1)=2$.
Now assume the theorem is true for all $n^{\prime}<n$. Then, we know that $ah(2,n-1)=2$. Suppose we have a RF-coloring of $[2]^{n}$ with r colors (where $r=ah(2,n)-1$). Then since $[2]^{n}$ contains two layers of $[2]^{n-1}$ ($L_{1}$ and $L_{2}$), we have that $r\leq 2$, since each $L_{i}$ must contain one color. Since the length of combinatorial lines in $[2]^{n}$ is 2 for all $n\in\mathbb{N}$ and that every line is rainbow free, lines that contain points on $L_{1}$ and $L_{2}$ must be monochromatic. Therefore, $L_{1}$ and $L_{2}$ must be colored monochromatically with the same color, which means $r=1$.
By induction, we know this to be true for all natural numbers n. ∎

We will first show that every copy of $[3]^{2}$ contains at most three distinct colors in a RF 10-coloring of $[3]^{3}$. For the sake of contradiction, suppose $\exists$ a partition in which a layer of $[3]^{2}$ contains 4 distinct colors. which we will designate $L_{1}$. Then the remaining 6 colors must be split among the other two layers, $L_{2}$ and $L_{3}$, since the coloring would no longer be RF if $L_{1}$ contains more than 4 colors. Notice that this implies some layer contains at least one distinct color (in actuality, it must be two distinct colors, but that observation is unnecessary for this proof) since we cannot have a layer with 5 colors. Let this layer be $L_{2}$. But if we consider the combinatorial line that contains points in all three layers which includes the distinctly colored point in $L_{2}$, we see that it must be rainbow, since two of the points are distinctly colored, meaning that the colors do not appear outside of their respective layers. Thus we contradict the RF assumption, so every layer must contain at most 3 distinct colors.
Now, we will show that there cannot be two copies which share more than one color with each other, which will help us prove that no copy can have less than 3 distinct colors. Again, for the sake of contradiction, assume $\exists$ two layers, $L_{1}$ and $L_{2}$, that share more than one color with each other. Sharing 3 colors with each other would result in a layer containing more than 4 colors, since 7 colors must be split among the 3 layers, among which $L_{1}$ and $L_{2}$ already contain 3 colors (meaning they can only hold one more color). Sharing 4 colors is essentially the same; a layer would have more than 5 colors, which contradicts the RF assumption. Thus, if two layers share more than one color with one another, they must share exactly two colors with each other. Suppose $L_{3}$ has $0\leq j\leq 3$ distinct colors. Then, any new color we add to the third layer must be shared with at least one of $L_{1}$ or $L_{2}$. Then, the remaining number of colors, $10-j-2$, must be split among the first two layers. But since $5\leq 10-j-2\leq 8$ and the first two layers are already sharing two colors, one of these two layers must always contain more than 4 colors, and we have a contradiction to the RF assumption. Thus, two layers cannot share more than one color with one another.
Now, we have the properties to prove that a layer cannot contain less than 3 distinct colors. The cases where a layer contains 0 distinct colors or 1 distinct color are trivial; in the former, that would imply 10 colors are split among the other two layers, guaranteeing a layer containing 5 or more colors. Similarly, in the latter, 9 colors split among the other two layers would also guarantee a layer containing 5 or more colors by the pigeonhole principle. The only case we would need to deal with is if a layer contains 2 distinct colors. For contradiction, suppose that we have a RF 10-coloring of $[3]^{3}$ with a layer, $L_{3}$, containing 2 distinct colors. Now, let $j_{1},j_{2}\in\{0,1\}$ be the number of colors shared with $L_{1}$ and $L_{2}$, respectively. Then the number of distinct colors split between $L_{1}$ and $L_{2}$ is: $10-j_{1}-j_{2}-2$, which is 6, 7, or 8. Note that in the case where the color shared with the other layers is the same, we subtract one, which will still result in a value of 6, 7, or 8. We notice in the case of 7 and 8 that one layer must contain four distinct colors by the pigeonhole principle, which contradicts the RF assumption. We now must deal with the case where 6 distinct colors are split between $L_{1}$ and $L_{2}$, i.e., when $L_{3}$ shares one color with $L_{1}$ and another with $L_{2}$. This means that $L_{3}$ has 4 colors total. With 6 colors that need to collectively appear on $L_{1}$ and $L_{2}$, we also know that $L_{1}$ and $L_{2}$ cannot share a color; otherwise, that color must not appear on $L_{3}$ and $L_{1}$ or $L_{2}$ is forced to contain more than 4 colors, which contradicts the RF assumption. Then, $L_{1}$ and $L_{2}$ must each contain colors distinct from one another, which means that $L_{1}$ and $L_{2}$ also contain 4 colors. But this coloring must contain a rainbow since $L_{3}$ contains distinct colors; any combinatorial line containing a distinctly colored point on $L_{3}$ and has two other points on $L_{1}$ and $L_{2}$ will be rainbow. Thus, we have a contradiction and each layer must contain exactly 3 distinct colors.
The three layers all sharing one color also follows from the previous statements; if any two layers share no colors, then any combinatorial line spanning the 3 layers containing a distinctly colored point on the third layer would be rainbow. We have now proven the lemma. ∎

By Lemma 4.1, we know that each layer contains 3 distinct colors and share one color, which we will denote c, with each other. Let $[3]^{3}=L_{1}\cup L_{2}\cup L_{3}$ where $L_{i}={ix_{2}x_{3}:x_{2},x_{3}\in[3]}$. We will define the combinatorial line described by $*x_{2}x_{3}$ to be a ”pillar line.” Since every pillar line must be RF, two points $jx_{2}x_{3}$ and $kx_{2}x_{3}$ on the pillar line must be the same color, implying the color must be c. Thus for every distinctly colored point, the associated pillar line must contain two points colored c. In other words, there are 18 points colored with c and thus. Since there are 9 distinct colors and 9 points remaining, there must be exactly 9 distinctly colored points. Thus, the shared color is dominant and the 10-coloring is minimal. ∎

Since there is a dominant color, we can algorithmically show that there are very few minimal RF 4-colorings of $[3]^{2}$. We will choose a starting point which will be colored with a nondominant color, then eliminate points along the same combinatorial line as the start, then repeating with the remaining points until we have a complete coloring. Since we are in two dimensions, there are two types of starting points: a point part of 3 combinatorial lines or a point part of 2 combinatorial lines.
In the first case, we immediately receive a minimal RF 4-coloring, since 7 points will have been colored after the first step. Since the start point is part of 3 combinatorial lines, one of the combinatorial lines is the diagonal. Thus, out of each column and row, atleast two points will have been colored. This means the remaining 2 uncolored points are not along the same row or column, and neither are part of the diagonal. Thus, coloring these two points with distinct colors results in a RF minimal coloring. These colorings are shown in Figure 5.

We know that every layer is either from $S_{1}$ or $S_{2}$. Notice that we cannot mix colorings between sets; if a layer is in $S_{1}$, then another layer being in $S_{2}$ will always result in rainbow pillar line. But if we have every layer being a coloring from $S_{1}$, which contains two elements, then atleast two of the layers have the same coloring. This coloring will always contain a rainbow pillar line since two distinct nondominant colors will appear on the same combinatorial line, contradicting the RF assumption. ∎

Note that the total number of combinations of layers from $S_{2}$ in $[3]^{3}$ would be $3!=6$. Stacking these in any arrangement would never result in rainbow pillar lines, so we must look at diagonals. We will order the layers the same way as in Lemma 3.2, i.e. $L_{i}$ refers to all points of the form $ix_{2}x_{3}$. Suppose $L_{1}$ is $s_{1}$. Consider the combinatorial line defined by $**1$. This line must be not be rainbow, thus the second layer cannot be $s_{2}$. Then the second layer must be $s_{3}$. But then the line $***$ would be rainbow. Thus, $L_{1}$ cannot be $s_{1}$. Now let $L_{1}$ be $s_{2}$. Then, $L_{2}$ cannot be $s_{1}$, or else the lines $*3*$ and $**3$ will be rainbow. Then, $L_{2}$ must be $s_{3}$, and verifying the 10 combinatorial lines that are not pillar lines and span the layers shows that this coloring would be rainbow free (since $L_{3}$ is forced to be $s_{1}$). Now let $L_{1}$ be $s_{3}$. Then, $L_{2}$ cannot be $s_{2}$, or else we would have the lines $*2*$ and $**2$ will be rainbow. Then, $L_{2}$ must be $s_{1}$, and we can once again easily verify this coloring is rainbow free. Thus, out of the 6 possible combinations of layers, we only have two rainbow free colorings. The full list of colorings is shown in the below. We will denote the coloring on the top as ”Pattern 1” and the coloring on the bottom as ”Pattern 2.” In Figure 8, you can view the remaining 4 combinations that do not work. The rainbow combinatorial line will be highlighted in red, with each row representing a separate 10 coloring of $[3]^{3}$.

∎

For the sake of contradiction, suppose we have a coloring where a layer contains 10 distinct colors. Since $ah(3,3)=11$, we cannot have any more colors on that layer. The remaining 17 colors must be split among the last two layers, but this guarantees that a layer will have some number of distinct colors. Any pillar line containing one of those distinct colors will always be rainbow, since it contains two distinctly colored points. We arrive at a contradiction and conclude that a layer cannot contain 10 distinct colors. ∎

For contradiction, suppose we have two layers, $L_{1}$ and $L_{2}$ without loss of generality, that share two colors with each other. Let j be the number of colors shared between $L_{3}$ and $L_{2}$. The reason why we do not need to consider the number of colors shared between $L_{1}$ and $L_{3}$ is because if we can find a contradiction with $L_{1}$ and $L_{3}$ sharing no colors, we can easily find one when they do share colors (since the number of colors $L_{1}$ can hold is lessened). We will derive a contradiction based on j and the number of colors each layer can hold. Let $C_{1},C_{2},C_{3}$ define the maximum number of colors each layer can hold. Then, $|C_{1}|=8$, $|C_{2}|=8-j$, and $|C_{3}|=10-j$. Suppose $j\geq 2$. Then, $|C_{1}|=8,|C_{2}|\leq 6$, and $|C_{3}|\leq 8$. The maximum total numbers of colors all layers can hold is $C=26-2j\leq 22$. Thus for all $j\geq 2$, we will have an ”overflow” and have to put atleast one color onto a full layer, which guarantees 11 colors on a layer and thus a rainbow since $25-j>C$. We now deal with the cases where $j=0$ and $j=1$.
Case 1: $j=1$ If $j=1$, then $|C_{1}|=8,|C_{2}|=7$, and $|C_{3}|=9$, with $C=24$. Since we have $25-j=24$ colors left, we must fill up every single layer. In other words, each layer contains 10 colors. But since each layer is also rainbow-free and there are only two RF 10-colorings of $[3]^{3}$, we will have two layers $L_{i}$ and $L_{j}$ with the same ”pattern,” where the nondominant colors are in the same position. $L_{i}$ and $L_{j}$ share at most two nondominant colors. Regardless, we can choose a pillar line in which the two points are not colored with the shared nondominant colors. Since the third layer cannot be the same pattern, or else we would automatically have some rainbow pillar line, it must be the other pattern. Then, the third point on our chosen pillar line is colored with the dominant color. If the dominant color is not a shared color, we have a rainbow. If the dominant color is shared, then either the pillar line will still be rainbow or another pillar line will be rainbow. The latter is true because if the dominant color is shared with another layer, it is either dominant or nondominant. If dominant, then the original pillar line would be rainbow, since the points on $L_{i}$ and $L_{j}$ are not colored with the dominant color. If nondominant on other layers, we can choose a line containing the dominant color and some point on $L_{i}$ or $L_{j}$ that is not colored with a shared nondominant color. We know this line exists because the dominant color can only appear once on $L_{i}$ or $L_{j}$ as a nondominant color, which means there are at most two out of nine pillar lines that do contain the dominant color. Either way, we have a rainbow pillar line.
Case 2: $j=0$ If $j=0$, then $L_{3}$ contains only distinct colors. Since $|C_{1}|=8,|C_{2}|=8$, and $|C_{3}|=9$, with $C=25$, the only possible coloring is if we make every layer contain the maximum amount of colors. But since there exists distinctly colored points on $L_{1}$ and $L_{2}$, any pillar line containing those points will be rainbow, as the point on $L_{3}$ will also be distinct. Note that we only need one distinct point from $L_{1}$ or $L_{2}$, not a line containing distinctly colored points from both.
In all cases, we have rainbow lines and thus contradictions. Therefore, no two layers can share more than one color with each other. ∎

We know that the layers must share some colors, as if no layers share colors, any pillar line would be rainbow. Now for the sake of contradiction, suppose we have layers $L_{1},L_{2},$ and $L_{3}$ where $L_{1}$ shares the color $c_{12}$ with $L_{2}$ and $L_{2}$ shares another color $c_{23}$ with $L_{3}$. We then have $|C_{1}|=9$, $|C_{2}|=8$, and $|C_{3}|=9$ with 25 colors left. We notice that even if $L_{3}$ and $L_{1}$ share a color, each $L_{i}$ must contain at least 8 distinct colors. Furthermore, two of the layers $L_{i}$ and $L_{j}$ will be RF 10-colorings, and as a result, they must be different patterns, or else we can find pillar lines with distinctly colored points on $L_{i}$ and $L_{j}$. There are two cases: $L_{1}$ or $L_{3}$ and $L_{2}$ are the RF 10-colorings, or $L_{1}$ and $L_{3}$ are the RF 10-colorings.
Case 1: $L_{1}$ or $L_{3}$ and $L_{2}$ are the RF 10-colorings. Without loss of generality, suppose that $L_{1}$ is the RF 10-coloring. If $c_{12}$ is not dominant in at least one of the layers, we are essentially done. The shared color only appears once on $L_{1}$ or $L_{2}$ say at $p_{1}$. Then, there are 26 pillar lines that do not contain $p_{1}$, all of which contain two points on $L_{1}$ and $L_{2}$ that are different colors. Even supposing that $L_{1}$ and $L_{3}$ share a color, there will still be atleast 5 pillar lines to choose from (which may be a lot more if the shared color does not appear many times on $L_{3}$). If $c_{12}$ is dominant on both of the layers, we can once again consider the pillar lines. In this subcase, there are only 18 pillar lines with different colors on $L_{1}$ and $L_{2}$, and if these are all rainbow-free, we then have combinatorial lines that have to be rainbow on all 6 possible arrangements of patterns on and placements of $L_{1}$ and $L_{2}$, which can be found in Appendix A due to the large size and number of images.
Case 2: $L_{1}$ and $L_{3}$ are the RF 10-colorings. If $L_{1}$ and $L_{3}$ share a color, this becomes case 1 since $L_{2}$ must now also be a RF 10-coloring. We assume that $L_{1}$ and $L_{2}$ share no colors. But this is also a contradiction; any pillar line containing a distinct color on $L_{2}$ is rainbow, since the points on $L_{1}$ and $L_{3}$ cannot possibly be the same.
In both cases, we arrive at a contradiction to the assumption that this 27-coloring is RF. Thus, all three layers must share exactly one common color. ∎

For contradiction, assume $\exists$ a RF 27-coloring of $[3]^{4}$. Then, all layers must share a color and $|C_{1}|=|C_{2}|=|C_{3}|=9$. The remaining 26 colors will be spread among the three layers, guaranteeing two RF 10-colorings, say on $L_{1}$ and $L_{2}$. Once again, these colorings must have different patterns. If the shared color is not dominant on $L_{1}$ or $L_{2}$, we have atleast 26 pillar lines containing differently colored points from $L_{1}$ and $L_{2}$. Since $L_{3}$ has 8 distinct colors, we know that there must be at least 7 rainbow pillar lines. Thus, the shared color must be dominant on $L_{1}$ and $L_{2}$. We can now refer to Appendix A to show that there must always be a rainbow combinatorial line, which is a contradiction. Thus, there does not exist a RF 27-coloring of $[3]^{4}$. In other words, $ah(3,4)\leq 27$ and applying Corollary 2.5 gives us $ah(3,n)\leq 3^{n-1}-2\cdot 3^{n-4}+2$ for all natural numbers n $>$ 4. ∎