Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to prove the following result, given as an exercise in my book:


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 $\bar{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$.

Any help will be appreciated. Thanks.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

We want to show that $$r(K_m+\bar{K_n},K_p+\bar{K_q}) \le \dbinom{m+p-1}{m}n + \dbinom{m+p-1}{p}q.\tag*{(1)}$$ When $n = q = 1$, $(1)$ becomes $$r(K_{m+1},K_{p+1}) \le \dbinom{m+p-1}{m} + \dbinom{m+p-1}{p} = \dbinom{m+p}{m} \tag*{(2)}.$$ This classical bound follows from the well-known inequality $$r(K_{m+1},K_{p+1}) \le r(K_{m},K_{p+1}) + r(K_{m+1},K_{p}) \tag*{(3)}.$$ (The inequality $(2)$ follows from $(3)$ by induction on $m + p$. For the base cases, observe that, e.g., $r(K_{2},K_{p+1}) = 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 \geq 2$ and $n$, $q \geq 0$, then $$r(K_m+\bar{K_n},K_p+\bar{K_q}) \leq r(K_{m-1}+\bar{K_n},K_p+\bar{K_q}) + r(K_m+\bar{K_n},K_{p-1}+\bar{K_q}).$$

Proof: Set $N = r(K_{m-1}+\bar{K_n},K_p+\bar{K_q}) + r(K_m+\bar{K_n},K_{p-1}+\bar{K_q})$ and two-color $E(K_N)$ arbitrarily with the colors red and blue. Choose $x \in V(K_N)$. By choice of $N$, it is easy to see that there must be either $r(K_{m-1}+\bar{K_n},K_p+\bar{K_q})$ red edges incident to $x$ or $r(K_m+\bar{K_n},K_{p-1}+\bar{K_q})$ 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+\bar{K_n}$, then we are done. If not, then by hypothesis they must contain a blue copy of $K_{p-1}+\bar{K_q}$. However, all of the edges from $x$ to $U$ are blue, so $x$ and the copy of $K_{p-1}+\bar{K_q}$ form a blue copy of $K_{p}+\bar{K_q}$. $\square$

We are nearly done. By induction on $m + p$, we have $$r(K_m+\bar{K_n},K_p+\bar{K_q}) \le \dbinom{m+p-2}{m-1}n + \dbinom{m+p-2}{p}q\\ + \dbinom{m+p-2}{m}n + \dbinom{m+p-2}{p-1}q,$$ and $$\dbinom{m+p-2}{m-1}n + \dbinom{m+p-2}{p}q + \dbinom{m+p-2}{m}n + \dbinom{m+p-2}{p-1}q = \dbinom{m+p-1}{m}n + \dbinom{m+p-1}{p}q.$$

Finally, for the base case, one can show by the same method as above that $r(K_1+\bar{K_n},K_1+\bar{K_q}) \le n + q$. This completes the proof.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.