Ramsey Theorey Proof

Here’s a cool proof that uses probabilistic methods. The theorem is due to Alon and Linial (1989) and the proof was explained by Prof. Asaf Ferber in MATH 244.

Theorem. Let where is large enough with respect to (that is, it falls within our Ramsey bounds). Let be a graph on vertices which is -regular with . Then contains a cycle of length divisible by .

Proof. Step 1. Every oriented graph with minimum “out degree” contains a cycle. Why? Pick an arbitrary starting vertex. Follow its out edge to . Now go outward from to . You can proceed in this fashion along at most edges before you MUST return to an already-visited vertex.

Step 2. We show that there exists a -coloring of the vertices of with the colors such that in each neighborhood every color appears at least once. Or at least we will show that the probability of this NOT happening is less than 1. Let denote the color of some vertex .

Step 3. Define an oriented graph on the same vertex set as in the following way. Add the edge AND . That is, if is colored with the -th color, then .

It follows from Step 1 that has minimum out degree at least 1 and therefore contains a cycle. Moreover, such a cycle must be divisible by k. This is true by the construction of ! Without loss of generality, suppose we start at a vertex with color 1. We can only get back to that vertex from a vertex with color . And we can only move from our starting vertex to vertices colored with color 2 (and, in general, to a color we have not used yet). We need to move through all colors before ending up back where we started!

Now we need to prove that the coloring described in Step 2 exists. Define as follows. Each vertex picks a color from uniformly and independently at random. We define the event to be the case in which the neighborhood of a vertex is MISSING a color. Specifically, the color . This would have meant that we could not have drawn a directed edge in Step 3.

If we can show that the probability of the union of all ’s is smaller than 1, then as a consequence the probability of the intersection of the complements (``all vertices DO have a neighborhood with all colors’’) is non-zero! As before, we use the union bound and want to show that

It will be enough to demonstrate that each in the summation has a value less than where . We can think of as being

because we first must fix the vertex with one of the colors. Then, since is -regular, we repeat trials in which we are trying to NOT pick for the neighbor vertex the one color in the set of such that .

We can use what Jeremy Kun has called ``The Inequality’’ in an illuminating blog post that explains the inequality’s relation to probability: . Then we can substitute in . And since :

Since we defined the coloring to be at most the size of the vertex set of (), then is less than 1! So . And there is a non-zero probability that the coloring sketched out in Step 2 exists.

Thus contains a directed cycle that is divisible by . And we’re done! :eyeglasses:

26 Dec 2015