Ramseys Theorem can be extended to monochromatic subgraphs o

Ramsey’s Theorem can be extended to monochromatic subgraphs other than complete graphs.

(a) Give a coloring of the edges of K6 by red and blue (or by solid and dashed, if you don’t want to use actual colors) so that there no red K3 and no blue C4.

(b) Show that any coloring of the edges of K7 by red and blue contains a red K3 or a blue C4. (Hint: Consider two cases, one where there exists a vertex with at least four red edges incident to it and one where every vertex has at least 3 blue edges incident to it. You also need to justify that these cases cover everything.)

(c) Prove the following generalization of Ramsey’s Theorem: Given fixed graphs G and H, there exists p such that any coloring of the edges of Kp by red and blue contains a red copy of G or a blue copy of H. (Hint: Use Ramsey’s Theorem and the fact that every graph is a subgraph of a complete graph.)

(d) Show that it is always possible to color the edges of K2n red and blue so that there is no monochromatic perfect matching. Why doesn’t this conflict with the theorem in part (c)?

Solution

Hello ,

Please see the explanation below for question (C)

Theorem : If n 2 2 1( k 2) < 1, then R(k, k) > n.

Proof. One way to find a lower bound is to find a coloring of Kn without any monochromatic Kk . But this is hard, so colorings will be chosen at random. Let S be the set of colorings of Kn, so that |S| = 2( n 2) , and let P be the uniform distribution on S. Let f (x) = 1 is there exists no monochromatic Kk in the coloring and f (x) = 0 otherwise. Then, the goal is to show that P(f (x) = 1) > 0, or equivalently that P(f (x) = 0) < 1.

There are n k choices of k vertices in Kn, and each such choice is equivalent to a subgraph Kk of Kn.

The union bound of probability states that P(A B) P(A) + P(B), so P(f (x) = 0) n k P(a specific Kk is monochromatic) = n k 2 1( k 2) , since there are k 2 ways to color Kk and exactly two of them are monochromatic. Thus, R(k, k) 2 k/2 for all k 3, and thus the Ramsey numbers grow exponentially.

There’s the possibility of an exhaustive search. which takes exponential time and is unrealistic for large n, or a smarter way: if n = 2 k/2 , then n k 2 1( k 2) 1, so there is a very small probability that any given graph doesn’t have the property.

Since it’s easy to check, one can just randomly guess a graph, and guess again in the unlikely event that the graph is bad. Thus, this nonconstructive proof provides an algorithm.