Memoirs of the Amer. Math. Society. Amer. Math. Society, 2024.

[Erdős and Rado, 1952]
P. Erdős and R. Rado.
Combinatorial theorems on classifications of subsets of a given set.
Proceedings of the London Mathematical Society, 30 (2):0 417–439, 1952.

[Erdős and Szekeres, 1935]
Paul Erdős and George Szekeres.
A combinatorial problem in geometry.
Compositio Mathematica, 2:0 463–470, 1935.

[Feldman and Xiao, 2015]
Vitaly Feldman and David Xiao.
Sample complexity bounds on differentially private learning via communication complexity.
SIAM Journal on Computing, 440 (6):0 1740–1764, 2015.

[Francisco et al., 2015]
Christopher Francisco, Jeffrey Mermin, and Jay Schweig.
Catalan numbers, binary trees, and pointed pseudotriangulations.
Europ. J. Comb., 45, 04 2015.

[Frankl and Wilson, 1981]
Peter Frankl and Richard M. Wilson.
Intersection theorems with geometric consequences.
Combinatorica, 1:0 357–368, 1981.

[Furstenberg, 1977]
Harry Furstenberg.
Ergodic behavior of diagonal measures and a theorem of szemerédi on arithmetic progressions.
Journal d’Analyse Mathématique, 31:0 204–256, 1977.

[Furstenberg, 1981]
Harry Furstenberg.
Recurrence in Ergodic Theory and Combinatorial Number Theory.
Princeton University Press, 1981.

[Furstenberg and Weiss, 2003]
Hillel Furstenberg and Benjamin Weiss.
Markov processes and ramsey theory for trees.
Combinatorics, Probability and Computing, 120 (5–6):0 547–563, 2003.

[Gasarch, 2022]
William Gasarch.
Applications of ramsey theory to computer science.
<https://www.cs.umd.edu/ gasarch/TOPICS/ramsey/ramsey.html>, 2022.
Accessed: 25/03/2024.

[Graham et al., 1991]
R.L. Graham, B.L. Rothschild, and J.H. Spencer.
Ramsey Theory.
Wiley Series in Discrete Mathematics and Optimization. Wiley, 1991.

[Hanneke et al., 2023]
Steve Hanneke, Shay Moran, and Jonathan Shafer.
A trichotomy for transductive online learning.
In Proc. 37th Conf. Adv. Neural Information Processing Systems (NeurIPS), 2023.

[Hodges, 1997]
Wilfrid Hodges.
A shorter model theory.
Cambridge University Press, 1997.

[Inc., 2024]
The OEIS Foundation Inc.
On-line encyclopedia of integer sequences.
<https://oeis.org/>, 2024.
Accessed: 16/05/2024.

[Jung et al., 2020]
Young Hun Jung, Baekjin Kim, and Ambuj Tewari.
On the equivalence between online and private learnability beyond binary classification.
In Proc. 33rd Conf. Adv. Neural Information Processing Systems (NeurIPS), 2020.

[Kalavasis et al., 2022]
Alkis Kalavasis, Grigoris Velegkas, and Amin Karbasi.
Multiclass learnability beyond the PAC framework: Universal rates and partial concept classes.
In Proc. 35th Conf. Adv. Neural Information Processing Systems (NeurIPS), 2022.

[Kaplan et al., 2020]
Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer.
Privately learning thresholds: Closing the exponential gap.
In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2263–2285. PMLR, 2020.

[Kasiviswanathan et al., 2011]
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.
What can we learn privately?
SIAM J. Comput., 400 (3):0 793–826, 2011.

[Littlestone, 1987]
Nick Littlestone.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.
In Proc. 28th Symp. Foundations of Computer Science (FOCS), pages 68–77, 1987.

[Littlestone, 1988]
Nick Littlestone.
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.
Machine Learning, 2:0 285–318, 1988.

[Long, 2001]
Philip Long.
On agnostic learning with $\{0, *, 1\}$-valued and real-valued hypotheses.
In Proc. 14th Conf. Learning Theory (COLT), 2001.

[Milliken, 1979]
Keith R. Milliken.
A ramsey theorem for trees.
J. Comb. Theory, Series A, 260 (3):0 215–237, 1979.

[Pabbaraju, 2024]
Chirag Pabbaraju.
Multiclass learnability does not imply sample compression.
In Proc. 35th Intl. Conf. Algorithmic Learning Theory (ALT), 2024.

[Pach et al., 2012]
János Pach, Gábor Tardos, and József Solymosi.
Remarks on a ramsey theory for trees.
Combinatorica, 320 (4):0 473–482, 2012.

[Ramsey, 1930]
F. P. Ramsey.
On a problem of formal logic.
Proceedings of the London Mathematical Society, s2-30:0 264–286, 1930.

[Roberts, 1984]
Fred S. Roberts.
Applications of ramsey theory.
Disc. Appl. Math., 90 (3):0 251–261, 1984.

[Rosta, 2004]
Vera Rosta.
Ramsey theory applications.
Electronic Journal of Combinatorics, 1000, 2004.

[Shalev-Shwartz and Ben-David, 2014]
Shai Shalev-Shwartz and Shai Ben-David.
Understanding machine learning: From theory to algorithms.
Cambridge university press, 2014.

[Sivakumar et al., 2021]
Satchit Sivakumar, Mark Bun, and Marco Gaboardi.
Multiclass versus binary differentially private PAC learning.
In Proc. 34th Conf. Adv. Neural Information Processing Systems (NeurIPS), pages 22943–22954, 2021.

[Szemerédi, 1975]
Endre Szemerédi.
On sets of integers containing k elements in arithmetic progression.
Acta Arithmetica, 27:0 199–245, 1975.

[Vadhan, 2017]
Salil P. Vadhan.
The complexity of differential privacy.
In Tutorials on the Foundations of Cryptography, pages 347–450. Springer International Publishing, 2017.

[Valiant, 1984]
Leslie G. Valiant.
A theory of the learnable.
Commun. ACM, 270 (11):0 1134–1142, 1984.

[Wigderson, 2019]
Avi Wigderson.
Mathematics and Computation: A Theory Revolutionizing Technology and Science.
Princeton University Press, 2019.

§ UPPER BOUND FOR THE RAMSEY NUMBER FOR CHAINS

In the proof of <Ref> we showed the existence of the Ramsey number $\Ramsey(d,m,k)$. Here we give an explicit calculation for the sufficient depth $n$ that is required for the proof. Subsequently, we derive an upper bound for $\Ramsey(d,m,k)$.

The procedure described in the proof of <Ref> can be continued until step ${t=\Ramsey(d,m-1,k^2)}$ if for every sequence $\sigma$ of length $t$, $\mathtt{depth}(S_{\sigma}) \ge 0$. Consider a sequence $\sigma$ of length $t$. To ease the notation, for every step $i\in\{m-2,\ldots,t\}$, $\mathtt{depth}(S_{\sigma(i)})$ is denoted by $d_i$.
Recall, by <Ref> the following holds.

\begin{equation}\label{eq:inductive_theOG}
\left\{
\begin{array}{ll}
d_{m-2} &= n-(m-2),\\
d_{i+1} &\ge \left\lfloor\frac{d_i -1}{k^{i \choose {m-2}}}\right\rfloor.
\end{array}
\right.
\end{equation}

Observe that if $d_i \ge 2 k^{i \choose {m-2}}$ then

\begin{equation}\label{eq:recurrence_relation}
\left\lfloor\frac{d_i -1}{k^{i \choose {m-2}}}\right\rfloor \ge \frac{d_i}{k^{i \choose {m-2}}} - 1 \ge \frac{d_i}{2k^{i \choose {m-2}}}.
\end{equation}

If $d_i < 2 k^{i \choose {m-2}}$, then

\[
\left\lfloor\frac{d_i -1}{k^{i \choose {m-2}}}\right\rfloor \in\{0,1\} \;,
\]

meaning that the procedure terminates, or continues for one more last step, therefore we can assume that the bound in <Ref> holds in every step $i$.
By induction, using the recurrence relation in <Ref>,

\begin{equation}\label{eq:absolute_bound_on_depth}
d_i \ge \frac{n-(m-2)}{2^{i-(m-2)}k^{\sum_{j=m-2}^{i-1} \binom{j}{m-2} }} = \frac{n-(m-2)}{2^{i-(m-2)}k^{ \binom{i}{m-1} }} \;,
\end{equation}

because $\sum_{j=m-2}^{i-1} \binom{j}{m-2} = \binom{i}{m-1} $ (the left-hand-side counts the number $(m-1)$-subsets $S\subseteq [i]$, by partitioning them according to the largest element).
For the procedure to continue $t$ steps we require $d_t\geq1$.
Together with <Ref> we deduce the following bound:

\begin{equation*}
n \ge 2^{t-(m-2)}k^{ \binom{t}{m-1} } + (m-2).
\end{equation*}

Notice that for every $m,k\geq2$ and $t\geq m-2$,

\begin{equation*}
2^{t-(m-2)}k^{ \binom{t}{m-1} } + (m-2) \leq 2^{t-(m-2)}k^{t^{m-1}} + (m-2)\leq k^{2t^{m-1}}.
\end{equation*}

Therefore, choosing $n=k^{2t^{m-1}}$ is sufficient.
Recall that $t=\Ramsey(d,m-1,k^2)$, therefore the following recursive relation is obtained.

\begin{equation}\label{eq:ramsey_recursive_bound}
\Ramsey(d,m,k)\leq k^{2\Ramsey(d,m-1,k^2)^{m-1}}.
\end{equation}

From now on we will use the Knuth notation $a \uparrow b$ in place of $a^b$ to ease the calculations, and recall that the Knuth's operator is right-associative, i.e. $a \uparrow b\uparrow c = a \uparrow (b\uparrow c)$.
By applying <Ref> repeatedly we obtain the following bound

\begin{align*}
\Ramsey(d,m,k) &\le k^2 \uparrow \Ramsey(d,m-1,k^2) \uparrow (m-1)\\
&\leq  k^2 \uparrow (k^{2\cdot 2} \uparrow (m-1)) \uparrow \Ramsey(d,m-2,k^{2^2}) \uparrow (m-2)\\
&\leq  k^2 \uparrow (k^{2\cdot 2} \uparrow (m-1)) \uparrow (k^{2\cdot2^2} \uparrow (m-2)) \uparrow \Ramsey(d,m-3,k^{2^3}) \uparrow (m-3)\\
&\leq \ldots \\
&\leq k^2 \uparrow (k^{2\cdot 2} \uparrow (m-1)) \uparrow (k^{2\cdot2^2} \uparrow (m-2)) \uparrow \ldots \uparrow (k^{2\cdot 2^{m-2}} \uparrow 2) \uparrow \Ramsey(d,1,k^{2^{m-1}})\uparrow 1 \\
&= k^2 \uparrow (k^{2\cdot 2} \uparrow (m-1)) \uparrow (k^{2\cdot 2^2} \uparrow (m-2)) \uparrow \ldots \uparrow (k^{2\cdot 2^{m-2}} \uparrow 2) \uparrow dk^{2^{m-1}},
\end{align*}

where $\Ramsey(d,1,k)=dk$ by the pigeonhole principle (<ref>).

\begin{equation*}
R_i= \begin{cases}
dk^{2^{m-1}}\coloneqq R  & \text{if $i=1$;}\\[10pt]
k^{2\cdot 2^{m-i}\cdot i \cdot R_{i-1}}
& \text{if $1<i<m$;}\\[10pt]
k^{2\cdot R_{m-1}}
& \text{if $i=m$.}
\end{cases}
\end{equation*}

Using this notation, $\Ramsey(d,m,k) \leq R_m$.

For $2\leq i\leq m$,

\[R_i\leq \twr_{(i)}(c_i \cdot 2^{m-2}R\log k),\]

where[We use the convention $\sum_{k=n_1}^{n_2}f(k)=0$ if $n_2<n_1$, hence $c_2=4$.]

\[c_i=4+\sum_{j=3}^i{\frac{\max\{1,\log_{(j-2)}(2\cdot 2^{m-j}j\log k)\}}{2^{m-2}R\log k}}.\]

Proof by induction on $i$.
For $i=2$,

\[R_2=k^{4\cdot 2^{m-2} \cdot R}=\twr_{(2)}(c_2\cdot 2^{m-2}R\log k).\]

For $2<i<m$,

\begin{align*}
&= k^{2\cdot 2^{m-i}\cdot i \cdot R_{i-1}}\\
& =\twr_{(2)}\left[2\cdot 2^{m-i} i\log k \cdot R_{i-1}\right]
\\
&\leq \twr_{(2)}\left[2\cdot 2^{m-i}\cdot i\log k\cdot\twr_{(i-1)}(c_{i-1}\cdot 2^{m-2}R\log k)\right] \tag{by induction.}
\\
&=\twr_{(2)}\left[\twr_{(i-1)}\log _{(i-2)}(2\cdot 2^{m-i} i\log k)\cdot \twr_{(i-1)}(c_{i-1}\cdot 2^{m-2}R\log k)\right]
\\
&\leq\twr_{(2)}\left[\twr_{(i-1)}\left(\max \{1,\log _{(i-2)}(2\cdot 2^{m-i} i\log k)\}\right)\cdot \twr_{(i-1)}\left(c_{i-1}\cdot 2^{m-2}R\log k\right)\right]
\\
&\leq \twr_{(2)}\left[\twr_{(i-1)}(\max \{1,\log _{(i-2)}(2\cdot 2^{m-i} i\log k)\})+c_{i-1}\cdot 2^{m-2}R\log k)\right]
\tag{$\star$}
\\
&=\twr_{(2)}\left[\twr_{(i-1)}(c_i \cdot 2^{m-2}R\log k)\right]
\tag{definition of $c_i$.}
\\
&=\twr_{(i)}(c_i \cdot 2^{m-2}R\log k),
\end{align*}

where the inequality marked with $(\star)$ holds since

\[\twr_{(n)}(x)\cdot\twr_{(n)}(y)\leq \twr_{(n)}(x\cdot y)\]

for $x,y\geq1, n\geq2$.

The case $i=m$ follows because $R_m=k^{2\cdot R_{m-1}}\leq k^{2m\cdot R_{m-1}}$, and $k^{2m\cdot R_{m-1}}\leq \twr_{(m)}(c_m \cdot 2^{m-2}R\log k)$, by using the above calculation for $2<i<m$ one more time for $i=m$.

For every integers $m\geq 2,d\geq m,k\geq 2$,

\begin{equation*}
\Ramsey(d,m,k)\leq \twr_{(m)}(5\cdot 2^{m-2}dk^{2^{m-1}}\log k).
\end{equation*}

It suffices to bound

\[c_m= 4+\sum_{j=3}^m{\frac{\max\{1,\log_{(j-2)}(2\cdot 2^{m-j}j\log k)\}}{2^{m-2}R\log k}}.\]

Note that for every $3\leq j\leq m$,

\[\log_{(j-2)}(2\cdot 2^{m-j}j\log k)\leq 2\cdot 2^{m-j}\log k\leq 2\cdot 2^{m-2}\log k.\]

\[c_m\leq 4+ \sum_{j=3}^m{\frac{2\cdot 2^{m-2}\log k}{2^{m-2}R\log k}}= 4+\frac{2(m-2)}{dk^{2^{m-1}}}\leq 5.\]

§ MORE ABOUT TYPES

<Ref> states that for every coloring of $m$-subsets of a complete binary tree, there exists a deep subtree that is colored with at most $\tau(m)$ colors, where $\tau(m)$ is the number of possible types of $m$-subsets. As we mentioned in <ref>, $\tau(m)$ is optimal in the sense that if we color $m$-subsets according to their type, every subtree of depth at least $m-1$ must contain $m$-subsets of all possible types, and therefore cannot see less then $\tau(m)$ colors. It is interesting to note that the optimal number of colors $\tau(m)$ depends only on the size of the colored subsets $m$, rather than on $d$ or $k$, where $d$ is the desired depth of the subtree and $k$ is the number of colors used in the coloring.

We turn to calculate $\tau(m)$. Recall that a set of vertices $A$ is closed if for all $u,v\in A$ also $\LCA(u,v)\in A$, and the closure of $A$, denoted $\bar A$, is the minimal closed set containing $A$. Two sets $A_1, A_2$ are equivalent if there is an isomorphism $\varphi:\bar {A_1}\to \bar {A_2}$ that respects being left/ right descendant relation, and also $\varphi(A_1)=A_2$.
The types of $m$-subsets are the induced equivalence classes.
(See <ref>.)

The number of possible types for $m$-subsets $\tau(m)$ corresponds to the generalized Catalan number denoted as $C(2,m)$ in the On-line Encyclopedia of Integer Sequences (OEIS) [Inc., 2024] (A064062), for all $m \ge 1$. In particular, it holds that:

\begin{equation*}
\tau(m) = \sum_{k = 0}^{m-1} (m-k) \binom{m+k-1}{k} \frac{2^k}{m}, \; \text{ for all } m \ge 1.
\end{equation*}

Let us first introduce the notion of branch-marked binary trees (as defined by <cit.>). Let $T$ be any binary tree[The definition we consider for a binary tree is a directed tree of which every vertex has at most one left child and at most one right child.]
and $v$ one of its vertices: we call $v$ a branching vertex if it has two children. If $B$ is any set of branching vertices of $T$, we call the pair $(T,B)$ a branch-marked binary tree and unmarked all the vertices that are not in $B$. Now,  <cit.> showed that the number of all possible branch-marked binary trees with $m$ unmarked vertices is exactly equal to $C(2, m)$. As a consequence, it is sufficient to prove that there exists a bijection between the possible types of $m$-subsets and such trees, to conclude the proof.
In the following, we will show such a bijection.

First, let $A$ be an $m$-subset of a complete binary tree $T$ of depth $\ge m$ and let $\bar{A}$ be its closure. Denote by $T_A$ the binary tree that is isomorphic to $\bar A$ as a subtree of $T$; i.e. there is a bijection $\varphi$ between $\bar A$ and the vertices of $T_A$ that preserves the being left/right descendant relation. Note that by the definition of type, $ A'$ has the same type as $A$ if and only if $T_A=T_{A'}$ and also $A$ and $A'$ are mapped to the same set of vertices in $T_A$/ $T_{A'}$.

We claim that the pair $(T_A,\varphi(\bar A\setminus A))$ is a branch-marked binary tree with $m$ unmarked vertices. In other words, each vertex $v \in \bar{A} \setminus A$ corresponds to a branching vertex in $T_{A}$. Indeed, if $\varphi(v)$ were not a branching vertex then it would have either no children or only one child, and in both cases $\bar A\setminus\{v\}$ would be closed and containing $A$, which is a contradiction to the minimality of $\bar{A}$.

Denote by $\Phi$ the map that sends the type of a subset $A$ to the branched-marked binary tree $(T_A,\varphi(\bar A\setminus A))$. By the properties discussed above, $\Phi$ is well-defined and injective.
It remains to show that $\Phi$ is surjective. Given a branch-marked tree $(S,B)$ with $m$-unmarked vertices, embed $S$ in a complete binary tree. We claim that the type of the $m$-subset containing all of the unmarked vertices is mapped by $\Phi$ to $(S,B)$.
Denote by $A$ the $m$-subset of the unmarked vertices. It suffices to show that $\bar A=A\cup B$.

It is clear that $\bar A\subseteq A\cup B$ since $S$ is a tree (and therefore $A\cup B$ is closed). On the other hand, if there exists $v\in B\setminus \bar A$, pick the deepest such $v$. Since $v$ is a branching vertex it is also the $\LCA$ of its two children, which are vertices in $\bar A$ by the choice of $v$, and therefore must be itself in $\bar A$, a contradiction.

The number of possible types for $m$-subsets $\tau(m)$ satisfies $\tau(m)\leq \frac{2^{3m-2}}{\sqrt{\pi (m-1)}}$, for all $m\geq  1$.

We claim that the following chain of inequalities holds:

\begin{align*}
\tau(m) &= \sum_{k = 0}^{m-1} (m-k) \binom{m+k-1}{k} \frac{2^k}{m}\\
&\le \binom{2m-1}{m-1} 2^{m-1} = \binom{2m-2}{m-1} \frac{(2m-1)2^{m-1}}{m} \\
&= C_{m-1} 2^{m-1} (2m-1)\\
&\le \frac{4^{m-1} \cdot 2^{m-1} \cdot (2m-1)}{m\sqrt{\pi (m-1)}} = \frac{2^{3m-3} (2m-1)}{m\sqrt{\pi (m-1)}}\\
&\le \frac{2^{3m-2}}{\sqrt{\pi (m-1)}},\\
\end{align*}

where $C_{m-1}$ is the $(m-1)$-th Catalan number. The first inequality holds by <Ref>, if we upper bound every $2^k$ with $2^{m-1}$ and use the binomial equality:

\[
\sum_{k=0}^{n} \binom{m+k-1}{k} = \binom{m+n}{n},
\]

with $n=m-1$. The second-to-last inequality instead, where the right-hand quantity corresponds also to the asymptotical limits of Catalan numbers,  was proven by <cit.> for $m \ge 1$.

§ RAMSEY FOR INFINITE TREES

In this section, we discuss the case of coloring $m$-subsets of an infinite complete binary tree. By compactness, <ref> implies that for every such coloring, there exists a $\tau(m)$-chromatic subtree of arbitrarily large finite depth. However, we claim that this is not true that there exists an infinite $\tau(m)$-chromatic subtree.

For simplicity, we start by describing a coloring of pairs in an infinite tree that does not admit an infinite trichromatic subtree.
Given two incomparable vertices $u,v$, we say that $u$ is the left vertex and $v$ is the right vertex if $u$ is a left descendant of $\LCA(u,v)$, and $v$ is a right descendant of $\LCA(u,v)$.
Consider the following pairs-coloring of an infinite complete binary tree $T$:

* if $\{u,v\}$ is a left-pair then $\chi(\{u,v\})=\mathsf{red}$;

* if $\{u,v\}$ is a right-pair then $\chi(\{u,v\})=\mathsf{blue}$;

* if  $\{u,v\}$ are incomparable, and the depth of the left vertex is at least the depth of the right vertex, then $\chi(\{u,v\})=\mathsf{green}$;

* if  $\{u,v\}$ are incomparable, and the depth of the left vertex is smaller than the depth of the right vertex, then $\chi(\{u,v\})=\mathsf{yellow}$.

Indeed, every infinite subtree admits all four colors. Suppose by contradiction that there exists an infinite trichromatic subtree $T'$, and without loss of generality assume that it is colored by $\{\mathsf{red, blue, green}\}$.
Take a vertex $u$ in the left subtree of $T'$ and denote by $d$ its depth in the original tree $T$.
Since $T'$ is infinite, there is a vertex $v$ in the right subtree of $T'$ with a depth in $T'$ that is larger than $d$, hence its depth in $T$ is also larger than $d$. By the definition of the coloring, we must have $\chi(\{u,v\})=\mathsf{yellow}$ which is a contradiction.

This example can be generalized for $m\geq 2$: color all $m$-chains according to their type, and color all $m$-anti-chains (i.e. $m$-subsets such that every two vertices are incomparable) according to the permutation of their depths when ordering the vertices from left to right.

The minimum number $\tau_{\infty}(m)$ needed to guarantee the existence of an infinite $\tau_{\infty}(m)$ - chromatic subtree for any given coloring of $m$-subsets, satisfies $\tau_{\infty}(m)\geq m !+2^{m-1}$. In particular, $\tau_{\infty}=\omega(\tau(m))$.

§ ADDITIONAL PROOFS

§.§ Proof of the Pigeonhole Principle for Trees

We prove here a more general version of <Ref> of <ref>.

Let $T$ be a complete binary tree of depth $n$, and let $k\in \bbN$. Then for every vertex coloring of $T$ with $k$ colors $c_1,\ldots,c_k$, and every $a_1,\ldots, a_k\in\bbN$ such that $a_1+\ldots+a_k=n$, there exists a $c_i$-monochromatic subtree of depth $a_i$ for some $i\in[k]$.

Indeed, <Ref>  follows from <Ref> by setting each $a_i$ to be at least $d$, which is the desired depth for the monochromatic subtree in the statement of <Ref>.

We first prove the statement for $k=2$. We use induction on the depth $d$ of the tree. The base case $d=0$ is trivial. Consider an arbitrary coloring of a tree $T$ of depth $d$ with two colors, $c_1,c_2$. Assume without loss of generality that the color of the root $v_{root}$ is $c_1$.
Let $T_0,T_1$ be the left and right subtrees of $v_{root}$, respectively.
If there exists a $c_2$-monochromatic subtree of depth $a_2$ of either $T_0$ or $T_1$, then we are done. If not, since $(a_1-1)+a_2=d-1$, by induction there exist $c_1$-monochromatic subtrees $T_0'$ and $ T_1'$ of $T_0$ and $T_1$ of depth $a_1-1$. $v_{root}$ together with $T_0'$ and $T_1'$ yield a $c_1$-monochromatic subtree of $T$ of depth $a_1$.

For $k>2$, induct on the number of colors $k$. Consider a coloring of $T$ with $k$ colors $c_1,\ldots,c_k$, and let $a_1+\ldots +a_k=n$. Define a new coloring using $k-1$ colors by considering $c_{k-1}$ and $c_k$ as the same new color $c'$. By induction, either there exists a $c_i$-subtree of depth $a_i$ for $1\leq i\leq k-2$,  or there exists a $c'$-subtree of depth $a_{k-1}+a_k$. If the latter holds, then by the base case, when considering again $c_{k-1}$ and $c_k$ as distinct colors, we are done.

§.§ Proof of <Ref>

[Restatement of <Ref>]
Let $T$ be a complete binary tree of depth $n$. Then the number of its level-aligned subtrees of depth $d$ is upper bounded by $\binom{n}{d+1} \cdot 2^{n2^d}$.

By hypothesis, the subtrees are level-aligned i.e. the vertices at the same distance from the root lie at the same level in the original tree. For a fixed subtree $S$, we consider its levels to be labeled by numbers between $0$, corresponding to the root of $S$, and $d$ corresponding to its leaves. Let $l_i$ (for $i=0,\ldots, d$) be the level in $T$ corresponding to level $i$ in $S$ and let $a_i = l_i - l_{i-1}$ (for $i=1,\ldots, d$).

For a fixed sequence $\{l_i\}_{i=0}^{d}$, we first upper bound the number of possible subtrees $S$ that respect this choice of levels. Observe the following: for any vertex $v$ at a level $i$ the number of possible choices for children at level $i+1$ is exactly $2^{2(a_{i+1}-1)}$. Indeed, the number of left descendants of $v$ at level $l_{i+1}$ is $2^{a_{i+1}} / 2$, and the same goes for the right descendants, which implies that the number of possible couples is $2^{2(a_{i+1}-1)}$. The number of possible choices for a root instead is $2^{l_0}$. The number of possible subtrees respecting the choice of levels is then:

\begin{align*}
2^{l_0} \cdot \prod_{i=1}^{d} 2^{2(a_i -1) 2^{i-1}} &=\\
2^{l_0 + \sum_{i=1}^{d} 2^i(a_i -1)} &\le\\
2^{l_0 + 2^d\sum_{i=1}^{d}(a_i -1)} &\le\\
2^{l_0 + 2^d(n - d - l_0)} &\le 2^{n2^d}
\end{align*}

where we employed the fact that $l_0 + \sum_{i=1}^{d} a_i \le n$. Given that the number of possible choices of levels is $\binom{n}{d+1}$, we obtain the desired result.