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).

Not ‘eternity’, just measly . =^]

#corrections: ‘extended’, not ‘extend’ in paragraph 1?

Great pictures! I like the proof of (infinite) Ramsey’s theorem. Leader presented it last week. It’s cool.

For the Compactness Theorem, I think you want ‘A set of first-order sentences has a model iff each of its finite subsets has a model’.

Hmmm. I’ll have to think of how to use that to deduce finite Ramsey from infinite Ramsey.

@Z Norwood: It’s a bit silly of you to submit minor corrections via comments when you can edit the posts. Idiot.

You’re saying the Compactness Theorem can be used to deduce from infinite Ramsey (infinite monochromatic subgraph of 2-coloured ) the statement that ‘For any natural number , there exists some natural number such that whenever the is 2-colo[u]red, this colo[u]ring yields a monochromatic copy of as a subgraph’?

Thanks for the corrections! And regarding the Compactness Theorem, except for the fact that I’m saying it for not just 2-colorings but any -coloring, yes, that is what I’m saying. Leader talked about it for a few minutes in Budapest. It’s also stated here.:

PS How do you create a hyperlink in a comment?

EDIT: Thanks, Zach! Must have mistyped before.

PPS what do you recommend I use for Theorem environments? I just made “Theorem.” bold.

Sorry; in lecture, Leader is doing 2-colourings of hypergraphs, so I guess our generalisations are orthogonal or something.

If the ‘Leader’ hyperlink above worked, then you use the typical HTML way of linking:

La href=”url”RwordsL/aR,

except replace L with a less-than sign and R with a greater-than sign.

I think I’ve figured out how to do this with the Compactness Theorem (see above).

For define to be the (first-order) sentence that says ‘ is a function from an initial segment of to 2(, of course), and there does not exist an -monochromatic subset of of size .’

For let be the first-order statement ‘.’ (The s just mean that is a free variable in and .)

By the Compactness Theorem the set has a model if and only if each of its finite subsets has a model. (The phrase ‘ has a model’ means that there is some that satisfies every sentence in , ie, for which is true for every (and, of course, we treat and as the same in this phrasing): eg, if is the statement , then has no model; if is the statement then is satisfied by the empty set (and only the empty set).

Anywho, has a model if and only if Ramsey’s theorem is false, and every finite subset of has a model if and only if finite Ramsey is false.

Tell me if you object to that.

Corrected. Thanks! It’s good to have someone read/write this who knows a little something about what I’m writing. :-)

Pingback: RT Part 3; Hypergraphs and Other Generalizations | whateversuitsyourboat