Problem 1176

.

The idea is to proceed in the same way as in the proof of the two-color Ramsey theorem. We will then obtain an upper bound on the $n$-color Ramsey number, which we can in turn bound to arrive at the desired relation.

First, note that the $n$-color Ramsey theorem is of little interest when $n=1$ (we have $R_{1}(s_{1})=s_{1}$) or when $s_{n}=1$ (any graph with at least 1 vertex is suitable), and that the integers $s_{1}, \ldots, s_{n}$ play symmetric roles. We will then show by induction that the function $R_{n}$ is well-defined, and find an upper bound for it.

Suppose we have an integer $k$ such that $R_{n}(s_{1}, \ldots, s_{n})$ is well-defined whenever $\sum_{i=1}^{n} s_{i} \leq k: k=n$ is such an integer. Let's show that $R_{n}(s_{1}, \ldots, s_{n})$ is also defined when $\sum_{i=1}^{n} s_{i}=k+1$ and $s_{1} \geq \ldots \geq s_{n}$. For this, there are two cases.

- If $s_{n}=1$, we have already said that $R_{n}(s_{1}, \ldots, s_{n})=1$, which is therefore well-defined.
- If $s_{n} \geq 2$, we will show that $R_{n}(s_{1}, \ldots, s_{n}) \leq g$, where $g=2-n+\sum_{i=1}^{n} R_{n}[s_{1}, \ldots, s_{n}]_{i}$, and $[s_{1}, \ldots, s_{n}]_{i}$ denotes the $n$-tuple $(s_{1}, \ldots, s_{i-1}, s_{i}-1, s_{i+1}, \ldots, s_{n})$. Indeed, if $K_{g}$ is a complete graph with $g$ vertices, we color its edges with $n$ colors $C_{1}, \ldots, C_{n}$, and then choose any vertex $v$ of $K_{g}$. By the pigeonhole principle, there exists a color $C_{i}$ such that $v$ is connected to at least $g-1$ vertices, and thus to $R_{n}[s_{1}, \ldots, s_{n}]_{i}$ vertices by edges of color $C_{i}$: let $K'$ be the subgraph induced by this set of vertices. If $K'$ contains a complete subgraph $K_{s_{j}}$ of color $C_{j}$ (with $i \neq j$), then $K_{g}$ also contains this complete subgraph; if $K'$ contains a complete subgraph $K_{s_{i}-1}$ of color $C_{i}$, then by adding the vertex $v$ to this subgraph, we form a complete subgraph $K_{s_{i}}$ of $K_{g}$, which is entirely colored with $C_{i}$. By the induction hypothesis, we are necessarily in one of the two cases above: this means that $R_{n}(s_{1}, \ldots, s_{n})$ is well-defined, and at most equal to $g$.

In particular, since $n \geq 2$, we can deduce that $R_{n}(s_{1}, \ldots, s_{n})$ is bounded by the function $S_{n}(s_{1}, \ldots, s_{n})$, symmetric in its variables, such that $S_{n}(s_{1}, \ldots, s_{n-1}, 1)=1$ and $S_{n}(s_{1}, \ldots, s_{n})=\sum_{i=1}^{n} S_{n}[s_{1}, \ldots, s_{n}]_{i}$ if $s_{1} \geq \cdots \geq s_{n} \geq 2$.

Furthermore, let's study a combinatorial object: increasing paths in $\mathbb{Z}^{n}$: these are finite paths where one moves from one point to the next by adding 1 to one coordinate. The number of increasing paths from the origin $(a_{1}, \ldots, a_{n})$ to the endpoint $(b_{1}, \ldots, b_{n})$ is equal to the multinomial coefficient $\frac{(b_{1}+\cdots+b_{n}-a_{1}-\cdots-a_{n})!}{(b_{1}-a_{1})!\ldots(b_{n}-a_{n})!}$: we have simply decided the $b_{i}-a_{i}$ moments when we decided to increase the $i$-th coordinate.

If we denote $T_{n}(s_{1}, \ldots, s_{n})$ the number of increasing paths in $\mathbb{Z}^{n}$ from the origin $(1, \ldots, 1)$ to the endpoint $(s_{1}, \ldots, s_{n})$, then $T_{n}$ is symmetric in its variables. Moreover, $T_{n}(s_{1}, \ldots, s_{n-1}, 1) \geq 1 = S_{n}(s_{1}, \ldots, s_{n-1}, 1)$ and $T_{n}(s_{1}, \ldots, s_{n})=\sum_{i=1}^{n} T_{n}[s_{1}, \ldots, s_{n}]_{i}$ if $s_{1} \geq \cdots \geq s_{n} \geq 2$, so an immediate induction on $\sum_{i=1}^{n} s_{i}$ shows that $T_{n}(s_{1}, \ldots, s_{n}) \geq S_{n}(s_{1}, \ldots, s_{n})$. The result follows.