# An upper bound for a graph Ramsey number r(Km+bar Kn,Kp+bar Kq)<=((m+p−1)/m)n+((9m+p−1)/p)q

An upper bound for a graph Ramsey number
I am trying to prove the following result, given as an exercise in my book:
$r\left({K}_{m}+\overline{{K}_{n}},{K}_{p}+\overline{{K}_{q}}\right)\le \left(\genfrac{}{}{0}{}{m+p-1}{m}\right)n+\left(\genfrac{}{}{0}{}{m+p-1}{p}\right)q$
Here r(G,H) denotes the Ramsey number for the graphs G and H, i.e. the smallest positive integer t, such that any graph F of order t either contains G or $\overline{F}$ (the complement of F) contains H. The join of graphs G+H is defined as the graph obtained by first drawing $G\cup H$ and then filling out all possible edges between the vertices of G and H.
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Firetto8w
We want to show that
$\begin{array}{}\text{(1)}& r\left({K}_{m}+\overline{{K}_{n}},{K}_{p}+\overline{{K}_{q}}\right)\le \left(\genfrac{}{}{0}{}{m+p-1}{m}\right)n+\left(\genfrac{}{}{0}{}{m+p-1}{p}\right)q.\end{array}$
When n=q=1, (1) becomes
$\begin{array}{}\text{(2)}& r\left({K}_{m+1},{K}_{p+1}\right)\le \left(\genfrac{}{}{0}{}{m+p-1}{m}\right)+\left(\genfrac{}{}{0}{}{m+p-1}{p}\right)=\left(\genfrac{}{}{0}{}{m+p}{m}\right).\end{array}$
This classical bound follows from the well-known inequality
$\begin{array}{}\text{(3)}& r\left({K}_{m+1},{K}_{p+1}\right)\le r\left({K}_{m},{K}_{p+1}\right)+r\left({K}_{m+1},{K}_{p}\right).\end{array}$
(The inequality (2) follows from (3) by induction on m+p. For the base cases, observe that, e.g., $r\left({K}_{2},{K}_{p+1}\right)=p+1$
The fact that the desired inequality is an easy generalization of a classical result gives a strong hint as to the best way to approach the proof. Happily, (1) does indeed follow along the same lines as the standard proof of (2).
Claim: If m, $p\ge 2$ and n, $q\ge 0$, then
$r\left({K}_{m}+\overline{{K}_{n}},{K}_{p}+\overline{{K}_{q}}\right)\le r\left({K}_{m-1}+\overline{{K}_{n}},{K}_{p}+\overline{{K}_{q}}\right)+r\left({K}_{m}+\overline{{K}_{n}},{K}_{p-1}+\overline{{K}_{q}}\right).$.
Proof: Set $N=r\left({K}_{m-1}+\overline{{K}_{n}},{K}_{p}+\overline{{K}_{q}}\right)+r\left({K}_{m}+\overline{{K}_{n}},{K}_{p-1}+\overline{{K}_{q}}\right)$ and two-color $E\left({K}_{N}\right)$ arbitrarily with the colors red and blue. Choose $x\in V\left({K}_{N}\right)$. By choice of N, it is easy to see that there must be either $r\left({K}_{m-1}+\overline{{K}_{n}},{K}_{p}+\overline{{K}_{q}}\right)$ red edges incident to x or $r\left({K}_{m}+\overline{{K}_{n}},{K}_{p-1}+\overline{{K}_{q}}\right)$ blue edges incident to x. Without loss of generality, suppose that the latter holds. Let U denote the set of vertices u such that ux is blue. Now consider the edges among the vertices of U. If these contain a red copy of ${K}_{m}+\overline{{K}_{n}}$, then we are done. If not, then by hypothesis they must contain a blue copy of ${K}_{p-1}+\overline{{K}_{q}}$. However, all of the edges from x to U are blue, so x and the copy of ${K}_{p-1}+\overline{{K}_{q}}$ form a blue copy of ${K}_{p}+\overline{{K}_{q}}$
We are nearly done. By induction on m+p, we have
$r\left({K}_{m}+\overline{{K}_{n}},{K}_{p}+\overline{{K}_{q}}\right)\le \left(\genfrac{}{}{0}{}{m+p-2}{m-1}\right)n+\left(\genfrac{}{}{0}{}{m+p-2}{p}\right)q\phantom{\rule{0ex}{0ex}}+\left(\genfrac{}{}{0}{}{m+p-2}{m}\right)n+\left(\genfrac{}{}{0}{}{m+p-2}{p-1}\right)q,$
and
$\left(\genfrac{}{}{0}{}{m+p-2}{m-1}\right)n+\left(\genfrac{}{}{0}{}{m+p-2}{p}\right)q+\left(\genfrac{}{}{0}{}{m+p-2}{m}\right)n+\left(\genfrac{}{}{0}{}{m+p-2}{p-1}\right)q=\left(\genfrac{}{}{0}{}{m+p-1}{m}\right)n+\left(\genfrac{}{}{0}{}{m+p-1}{p}\right)q.$
Finally, for the base case, one can show by the same method as above that $r\left({K}_{1}+\overline{{K}_{n}},{K}_{1}+\overline{{K}_{q}}\right)\le n+q$. This completes the proof.