Ramsey number for paths

Question

Let $n = R(P_{r+1}, c)$ be the smallest integer such that if $K_n$ is $c$-edge-coloured, then it contains a monochromatic subgraph isomorphic to $P_{r+1}$, the path of length $r$. I need to show that $R(P_{r+1}, c) \leq r^c + 1$.

I believe that the best known bound is linear in terms of $r$, so this is really rough, but I still can't get anywhere. I have tried modifying the usual proof of Ramsey's theorem, showing that $R(s, t) \leq R(s - 1, t) + R(s, t - 1)$ (Erdos-Szekeres), but to no avail. I have also tried proving the bound: $$R(P_{r+1}, c) - 1\leq r(R(P_{r+1}, c - 1) - 1)$$ by partitioning a complete graph into a product of $r$ complete subgraphs. I do know know if this bounds holds, but if it did, I would get the desired answer.

Please help with hints, not complete solutions. Thank you.

Answer 1

You must prove the following claim:

Claim. Let $r$ and $c$ be two nonnegative integers. Let $n$ be an integer such that $n > r^c$. Assume that the edges of the complete graph $K_n$ have been colored with $c$ colors. Then, $K_n$ has a monochromatic path of length $r$. (A path is called monochromatic if all its edges have the same color.)

Proof. Let $1, 2, \ldots, n$ be the vertices of $K_n$. Let $V$ be the set of all these $n$ vertices. A walk $\left(v_1,v_2,\ldots,v_s\right)$ of $K_n$ will be called increasing if $v_1 < v_2 < \cdots < v_s$. Note that any increasing walk is a path.

Let $1, 2, \ldots, c$ be the $c$ colors. For each vertex $i \in V$ and each color $k \in \left\{1,2,\ldots,c\right\}$, let $f_{i,k}$ denote the maximum length of an increasing path starting at $i$ such that all edges of this path have color $k$. (This is well-defined, since the length-$0$ path $\left(i\right)$ always exists, and since a path in $K_n$ cannot have length $\geq n$.)

Now, let us assume (for contradiction) that $K_n$ has no monochromatic path of length $r$. Then, in particular, $K_n$ has no monochromatic increasing path of length $r$. Hence, any monochromatic increasing path has length $\leq r-1$. Therefore, $f_{i,k} \in \left\{0,1,\ldots,r-1\right\}$ for all $i$ and $k$. Now, for each $i \in V$, let $f_i$ be the $c$-tuple $\left(f_{i,1},f_{i,2},\ldots,f_{i,c}\right)$. This $c$-tuple belongs to the $r^c$-element set $\left\{0,1,\ldots,r-1\right\}^c$ (since $f_{i,k} \in \left\{0,1,\ldots,r-1\right\}$ for all $i$ and $k$). By the pigeonhole principle, we thus conclude that two of these $c$-tuples $f_1, f_2, \ldots, f_n$ are equal (since $n > r^c$). That is, there exist two vertices $v$ and $w$ such that $v < w$ and $f_v = f_w$. Consider these vertices $v$ and $w$. Now, let $k$ be the color of the edge $vw$, and observe that $f_v = f_w$ entails $f_{v,k} = f_{w,k}$.

Now, take a longest increasing path starting at $w$ whose edges all have color $k$. This path has length $f_{w,k}$ (by the definition of $f_{w,k}$). Let us now extend this path by inserting the vertex $v$ (and the edge $vw$) at its front. The result is a walk of length $f_{w,k}+1$ that starts at $v$ and has the property that all its edges have color $k$ (since the edge $vw$ has color $k$). This walk furthermore is increasing (since $v < w$), and thus is a path. Hence, we have found an increasing path of length $f_{w,k}+1$ that starts at $v$ and has the property that all its edges have color $k$. Therefore, $f_{v,k} \geq f_{w,k}+1 > f_{w,k}$, which contradicts $f_{v,k} = f_{w,k}$. This shows that our assumption was false, and thus the claim is proved.

Remark. This can be generalized: If $D$ is a tournament with more than $r^c$ vertices, and if the arcs of $D$ are colored with $c$ colors, then $D$ has a monochromatic path of length $r$. This is a particular case of Theorem 2 in Yannis Manoussakis, Zsolt Tuza, Ramsey numbers for tournaments, Theoretical Computer Science 263, Issues 1--2, 28 July 2001, Pages 75--85. The proof in the general case is more complicated. Note that this general result also generalizes Redei's little theorem, which says that every tournament has a Hamiltonian path. (Just take $c = 1$ to recover this.)

Answer 2

Notation:

• We will denote a complete graph of order $a$ (also called $a$-clique) as $\mathbb K[a]$.
• Any general graph of order $a$ will be denoted by $\mathbb G[a]$.
• the colored degree of a vertex is the number of edges of a particular color emerging out of that vertex. $\#c(v)$ denotes the number of $c$-colored edges emerging out of $v$.

define $P(m,n) = R(\mathbb P[m],\mathbb K[n])$ . that is the smallest number $R$ for which a red-blue coloring of the edges of $\mathbb K[R]$ either contains a red $\mathbb P[m]$ or a blue $\mathbb K[n]$. Note, that path length is usually measured by the number of edges, but here $m$ denotes the number of vertices in the path.

we claim that ${P(m+1,n+1) \le P(m+1,n) + P(m,n+1) = T} \ \ \ \ \ \ \ \ \ \ (1) $.

construct a red-blue coloring of $\mathbb K[T]$. the degree of any vertex is ${P(m+1,n) + P(m,n+1) -1}$. suppose there exists $v^*$ such that $\#r(v^*) \ge P(m,n+1)$

indeed, if we have a blue $\mathbb K[n+1]$ , we are done. if we have a red $\mathbb P[m]$, join to $v^*$ by red edge. and we are done.

Else, all vertices have $\#r(v) < P(m,n+1)$. hence $\#b(v) > P(m+1,n) -1$. So indeed, ${\#b(v) \ge P(m+1,n)}$.

if we have a red $\mathbb P[m+1]$, we are done. if we have a blue $\mathbb K[n]$, $v$ is adjacent to $\mathbb K[n]$ via all blue edges, hence, we are done.

notice that $P(m,2) = m, P(n,2) = n$. Hence, we can use a double induction (using inequality $(1)$) to show that $P(m,n) \le (m-1)(n-1) + 1$.

we claim that $P(m,n) = (m-1)(n-1) + 1$.

suppose $P(m,n) \le (m-1)(n-1)$. This will act as a base case for our inductive descent into absurdity.

we will show that if $r < min((m-1)(n-2)),((m-2)(n-1))$ , ${P(m,n) \le (m-1)(n-1) -r }$ implies $P(m,n) \le (m-1)(n-1) -r -1$. that is we can safely delete a vertex.

let $T' = (m-1)(n-1) - r$. construct a red-blue coloring of $\mathbb K[T']$. Now, suppose ${P(m,n) \le (m-1)(n-1) -r }$.

given that $r < min((m-1)(n-2)),((m-2)(n-1))$, if we find a red $\mathbb P[m]$ , the remaining vertices are $(m-1)(n-2) - r$ in number, which is greater than zero. So delete one vertex from this. Similarly, if we find a blue $\mathbb K[n]$, the remaining verticles are $(m-2)(n-1) - r$ in number, which is greater than zero, so we can delete 1 vertex from this.

Hence, the induction is closed reaching ${ r = min((m-1)(n-2)),((m-2,n-1))}$.

so suppose $m<n$. then, $r = (m-2)(n-1)$.

indeed, it must be that ${P(m,n) \le (m-1)(n-1) - (m-2)(n-1)}$. Hence, $P(m,n) \le n-1$. Color all edges of $\mathbb K[n-1]$ blue. Then, we neither have a blue $\mathbb K[n]$ nor a red $\mathbb P[m]$, reaching a contradiction.

Similarly, let $m\ge n$. Then, $r =(m-1)(n-2)$. we get $P(m,n) \le m-1$. color all edges of $\mathbb K[m-1]$ red. we neither have a blue $\mathbb K[n]$ nor a red $\mathbb P[m]$, again reaching a contradiction.

The thing is, our induction step is correct. Therefore, the base case must be wrong. Hence $P(m,n) > (m-1)(n-1)$. Arriving at the desired result.

Define $P^*(a_1,a_2,...a_n) = R(\mathbb P[a_1],\mathbb P[a_2],... , \mathbb P[a_n])$.

Now, notice that $P(a_1,a_2,...a_n) \le P(a_1, P^*(a_2,..a_n)) = (a_1-1)(P^*(a_2,..a_n) - 1) + 1$.

Applying this recursively, we get that $P^*(a_1,a_2,...a_n) \le \prod_{i=1}^{n} (a_i -1) + 1.$ Setting each ${a_i = a}$, we obtain the desired result.

Answer 3

We proceed by induction on $c$.

When $c = 1$, $R(P_{r + 1}, 1) \leq r + 1$, since $K_{r + 1}$ contains all possible edges between $r + 1$ vertices, and a path of length $r$ is one such choice.

Let $n = R(P_{r+1}, c)$, $G = K_n$. Let $G$ be $(c - 1)$-edge-coloured, and extend this to a $c$-edge-colouring of $H = K_{n + \lfloor r/2 \rfloor}$, where the new complete subgraph $K_{\lfloor r/2 \rfloor}$ is $1$-edge-coloured for a previous colour used in $G$, and all of the edges linking $G$ to this subgraph are $1$-edge-coloured in a new colour. This is a graph with no monochromatic path of length $r$, so: $$R(P_{r+1}, c) \leq R(P_{r}, c - 1) + \lfloor r/2 \rfloor$$ So, by the induction hypothesis: $$R(P_{r+1}, c) \leq r^{c-1} + 1 + \lfloor r/2 \rfloor \leq r^c + 1$$ And this last inequality is true since: \begin{align*} &r^{c-1} + 1 + \lfloor r/2 \rfloor \leq r^c + 1 \\ \iff &\lfloor r/2 \rfloor \leq r^{c-1}(r - 1) \end{align*} If $r$ is even, then $r \geq 2$ and: $$\frac{1}{2} \leq r^{c - 2}(r - 1)$$ This last inequality might not hold if $c = 1$, but in that case: $$\frac{1}{2} \leq 1 - \frac{1}{r}$$ and since $r \geq 2$, this is true.

If $r$ is odd, then $r \geq 1$ and: $$\frac{r - 1}{2} \leq r^{c - 1}(r - 1) \iff \frac{1}{2} \leq r^{c - 1}$$ Q.E.D.

Answer 4

In fact, a more general recurrence holds: $$R(T_{r+1}, c) - 1\leq r(R(T_{r+1}, c - 1) - 1)$$ where $T_{r+1}$ is any fixed $(r+1)$-vertex tree.

This starts from the clique-tree Ramsey number result of Chvátal (see this MSE post, for example) that $R(T_{r+1}, K_{s+1}) \le rs+1$: any $2$-coloring of $K_{rs+1}$ either contains a $T_{r+1}$ in the first color or a $K_{s+1}$ in the second. (Actually, Chvátal proved that $R(T_{r+1}, K_{s+1})=rs+1$, but the lower bound will not extend to our application of this bound.)

In our case, set $s = R(T_{r+1},c-1)-1$; to prove the recurrence, take a $c$-coloring of $K_{rs+1}$, but treat all colors except the first as identical for now. Either we get a $T_{r+1}$ in the first color, or a $K_{s+1}$ in the second. In the latter case, we have found a $(c-1)$-colored complete graph on $s+1 = R(T_{r+1},c-1)$ vertices, which by definition must also contain a monochromatic $T_{r+1}$.

This proves that $R(T_{r+1}, c)$ is at most $rs+1$, or $r(R(T_{r+1},c-1)-1) + 1$. Starting from $R(T_{r+1},1) \le r+1$, which hold just because $K_{r+1}$ contains $T_{r+1}$, we can show $R(T_{r+1},c) \le r^c+1$ by induction on $c$.

Actually, even more is true: if $T^1, T^2, \dots, T^c$ are $c$ trees, not necessarily all the same, with $r_1+1, r_2+1, \dots, r_c+1$ vertices respectively, the same argument tells us that $$R(T^1, T^2, \dots, T^c) \le r_1 r_2 \cdots r_c + 1.$$