Friends and I came across this problem in our Graph Theory course:
We need to show that $$R_k(C_4,...,C_4)\leq k^2+2k, \forall k\geq 2 $$
Our attempt was by induction on $k$, we managed to do the induction base as well, but we don't know how to advance. Hopefully someone can complete our proof or give us a hint.
Induction base:
Let $k=2$, then $2^2+2\cdot2=8$, so we need to show that there is either a blue or a red $C_4$ in every (red and blue) two-coloring of $K_8$.
Since $8>6=R(3,3)$, we know that there is a blue or red triangle in $K8$. Denote $u_1,...,u_5$ the vertices not in the triangle, let's assume w.l.o.g. that this triangle is red.
If for any $i$ two edges from the triangle to $u_i$ are red, then we have a red $C_4$.
So assume, from each $u_i$ we have at most one red edge into the triangle, i.e. we have at least two blue edges into the triangle from every $u_i$.
Since we have more vertices outside of the triangle than in the triangle, we can find $i$ and $j$ where $u_i$ and $u_j$ have two blue edges to the same two vertices in the triangle (denote them by $v_1$ and $v_2$). Now we have a blue $C_4$ with edges $(u_i,v_1);(v_1,u_j);(u_j,v_2);(v_2,u_i)$.
Induction step
This is where we need help.
Regards
Nik
Consider any fixed coloring of edges of a complete graph $K_n$ with $n>1$ vertices into colors $1,\dots, k$ without monochromatic copies of $K_4$. Lets double count the quantity $N$ of pairs $(e,v)$ where $e=uw$ is and edge of $K_n$ such that edges $uv$ and $wv$ are monochromatic. Since there are no monochromatic copies of $K_4$, each edge $e$ of $K_4$ can participate in at most $k$ pairs $(e,v)$ which we count. Thus $N\le k{n\choose 2}$. On the other hand, let $v$ be any vertex of $K_n$. For each color $i$ let $n_i$ be the quantity of vertices $u$ of $G$ such that an edge $uv$ is colored in a color $i$. Then $v$ participates in $N_i=\sum_{i=1}^k {n_i\choose 2}$ pairs $(e,v)$ which we count. Using the inequality between arithmetic and quadratic means, we have
$$N_i=\sum_{i=1}^k {n_i\choose 2}=\frac 12\sum_{i=1}^k n_i^2-n_i\ge$$ $$ \frac 12\left(\frac{(\sum n_i)^2}{k}- \sum n_i \right) =\frac {(n-1)^2-k(n-1)} {2k}.$$
Thus $N=\sum_{i=1}^n N_i\ge\frac {n(n-1)(n-k-1)}{2k}$ and we have a contradiction provided $\frac {n(n-1)(n-k-1)}{2k}> k{n\choose 2}$, that is when $\frac {n-k-1}{k}> k$, or $n>k^2+k+1$. Thus $R_k(C_4,\dots,C_4)\le k^2+k+2$.