Last time we showed that , the complete graph on vertices has a monochromatic triangle (i.e. a complete graph on vertices) whenever the edges of it are 2-colored. And we asserted that this can be extended to: For any natural number , there exists some natural number such that whenever the is 2-colored, this coloring yields a monochromatic copy of as a subgraph.
In this post I wanted to discuss what happens when we generalize 2-coloring to -coloring, and/or generalize the search for a monochromatic copy of to that of a monochromatic copy of a complete graph on infinitely many vertices.
I will actually do these two things together. I will discuss -colorings of infinite graphs, of which -coloring finite graphs is a special case.
So what about for infinite graphs? Say we have the complete graph on vertices. For instance, say each positive integer is a vertex, and each vertex is connected to every other vertex. Then say that we -color the edges of this graph. Can we guarantee an infinite monochromatic subgraph? i.e. an infinite set of vertices such that given any pair of vertices, the color of the edge between that pair is the same as the color between any other pair of the vertices in this set.
Well, once again, the answer is yes. This is one of the 500 or so results called Ramsey’s Theorem. Let’s sketch a proof for it.
Say the edges of the complete graph on the vertex set are -colored. Pick some . There are infinitely many edges emanating from . Since these infinitely many edges were colored using only colors, some color, call it , must be the color of infinitely many of those edges. Set to be the infinite subset of such that all edges from to are colored .
By the same reasoning we can pick any and pick and such that there are infinitely many edges from to of color and .
Now repeat this process forever. Then, once you have reached eternity, take a step back and see what properties you devoted that time to uncovering. Notice that we get a list of distinct vertices and (not distinct as we will soon see) colors such that the edge has color . Moreover, each has infinitely many vertices and is properly contained within .
Now, since infinitely many were chosen, and we only have (some finite number) of colors, infinitely many of the must be the same, say . Then the graph induced by is monochromatic.
Why? Because the s are nested. So each is connected to each other by an edge of color (say, red), like so.
There are two ways that I am aware of from which the finite case can be deduced from the infinite. The first is a proof by contradiction. The way the proof goes is that you construct sets of -colorings of each finite complete graph that avoids a monochromatic complete graph of a fixed size. Essentially, the “intersection” of these is nonempty — where if one coloring is a restriction of another then you consider them the same in the intersection. This is the case because you assume there is one for every graph, and each coloring for one graph restricts to each smaller graph. So we can build a coloring of the infinite graph in this fashion, which is equivalent to choosing one from the intersection. However, this then contradicts what we just proved.
Or, you can just observe that it follows from the compactness theorem which states that a first-order sentence has a model if and only if every finite subset of it has a model… whatever that means. (Please send all your questions about the previous statement to Z Norwood, one of this blog’s other authors).
EDIT: For details on the previous statement, see Z Norwood’s comment below.
Lastly, I will state but not discuss an interesting result know as the Canonical Ramsey Theorem.
Theorem. Let be a coloring of with an arbitrary set of colors. Then there exist an infinite on which either
- is constant on , OR
- is injective on , OR
- (ij) = (k,l) if and only if , OR
- (ij) = (kl) if and only if .
In the next post we will be coloring positive integers instead of edges of graphs. And instead of monochromatic subgraphs the “structure” that we will look to find is a monochromatic arithmetic progression.
(O, and by the way, in case these results didn’t knock your socks off yet, by induction every result I’ve stated so far (except maybe this last one) generalizes to hypergraphs).