7
$\begingroup$

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

$r(K_m+\bar{K_n},K_p+\bar{K_q})\le\binom{m+p-1}{m}n+\binom{m+p-1}{p}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 $\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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.