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
Haven Kerr
Answered question
2022-09-15
An upper bound for a graph Ramsey number 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 (the complement of F) contains H. The join of graphs G+H is defined as the graph obtained by first drawing and then filling out all possible edges between the vertices of G and H.
Answer & Explanation
Firetto8w
Beginner2022-09-16Added 8 answers
We want to show that
When n=q=1, (1) becomes
This classical bound follows from the well-known inequality
(The inequality (2) follows from (3) by induction on m+p. For the base cases, observe that, e.g., 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, and n, , then . Proof: Set and two-color arbitrarily with the colors red and blue. Choose . By choice of N, it is easy to see that there must be either red edges incident to x or 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 , then we are done. If not, then by hypothesis they must contain a blue copy of . However, all of the edges from x to U are blue, so x and the copy of form a blue copy of We are nearly done. By induction on m+p, we have
and
Finally, for the base case, one can show by the same method as above that . This completes the proof.