## Ramsey Theory Part 2; RT on Infinite, Colorful Graphs

Last time we showed that $K_6$, the complete graph on $6$ vertices has a monochromatic triangle (i.e. a complete graph on $3$ vertices) whenever the edges of it are 2-colored.  And we asserted that this can be extended to:  For any natural number $n$, there exists some natural number $N$ such that whenever the $K_N$ is 2-colored, this coloring yields a monochromatic copy of $K_n$ as a subgraph.

In this post I wanted to discuss what happens when we generalize 2-coloring to $k$-coloring, and/or generalize the search for a monochromatic copy of $K_n$ 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 $k$-colorings of infinite graphs, of which $k$-coloring finite graphs is a special case.

So what about for infinite graphs?  Say we have the complete graph on $\aleph_0$ vertices.  For instance, say each positive integer is a vertex, and each vertex is connected to every other vertex.  Then say that we $k$-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 $\mathbb{N}$ are $k$-colored.  Pick some $a_1 \in \mathbb{N}$.  There are infinitely many edges emanating from $a_1$.  Since these infinitely many edges were colored using only $k$ colors, some color, call it $c_1$, must be the color of infinitely many of those edges.  Set $B_1$ to be the infinite subset of $\mathbb{N} \setminus \{a_1\}$ such that all edges from $a_1$ to $B_1$ are colored $c_1$.

By the same reasoning we can pick any $a_2 \in B_1$ and pick $c_2$ and $B_2$ such that there are infinitely many edges from $a_2$ to $B_2$ of color $c_2$ and $B_2 \subseteq (B_1 \setminus \{a_2\})$.

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 $a_1, a_2, a_3 \dots$ and (not distinct as we will soon see) colors $c_1, c_2, c_3, \dots$ such that the edge $ij$ has color $c_i$.  Moreover, each $B_i$ has infinitely many vertices and is properly contained within $B_{i-1}$.

Now, since infinitely many $c_i$ were chosen, and we only have $k$ (some finite number) of colors, infinitely many of the $c_i$ must be the same, say $c_{i_1} = c_{i_2} = c_{i_3} = \dots$.  Then the graph induced by $a_{i_1}, a_{i_2}, \dots$ is monochromatic.

Why?  Because the $B_{i_k}$s are nested.  So each $a_{i_m}$ is connected to each other $a_{i_n}$ by an edge of color $c_i$ (say, red), like so.

$\square$

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 $k$-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 $c: \mathbb{N}^{(2)} \rightarrow X$ be a coloring of $\mathbb{N}^{(2)}$ with an arbitrary set of colors.  Then there exist an infinite $M \subseteq \mathbb{N}$ on which either

1. $c$ is constant on $M^{(2)}$, OR
2. $c$ is injective on $M^{(2)}$, OR
3. $c$(ij) = $c$(k,l) if and only if $i=k$, OR
4. $c$(ij) = $c$(kl) if and only if $j=l$.

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

I am a fifth year mathematics Ph.D. student at UCSD.
This entry was posted in Ramsey Theory. Bookmark the permalink.

### 9 Responses to Ramsey Theory Part 2; RT on Infinite, Colorful Graphs

1. Z Norwood says:

Not ‘eternity’, just measly $\omega$. =^]
#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 says:

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

• Z Norwood says:

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

• JCummings says:

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 $k$-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.

• JCummings says:

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

• Z Norwood says:

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

La href=”url”RwordsL/aR,
except replace L with a less-than sign and R with a greater-than sign.

• Z Norwood says:

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

For $m \in \mathbb{N}$ define $\phi(x)$ to be the (first-order) sentence that says ‘$x$ is a function from an initial segment of $\mathbb{N}$ to 2($=\{0,1\}$, of course), and there does not exist an $x$-monochromatic subset of $\mathrm{dom}(x)$ of size $\ge m$.’
For $n \in \mathbb{N}$ let $\psi_n(x)$ be the first-order statement ‘$\left| \mathrm{dom}(x) \right| \ge n$.’ (The $(x)$s just mean that $x$ is a free variable in $\phi$ and $\psi_n$.)

By the Compactness Theorem the set $A = \{\phi\} \cup \{\psi_n : n\in \mathbb{N}\}$ has a model if and only if each of its finite subsets has a model. (The phrase ‘$X$ has a model’ means that there is some $a$ that satisfies every sentence in $X$, ie, for which $\rho(a)$ is true for every $\rho \in X$ (and, of course, we treat $\{\rho\}$ and $\rho$ as the same in this phrasing): eg, if $\rho(x)$ is the statement $x \neq x$, then $\rho(x)$ has no model; if $\rho(x)$ is the statement $\forall z (z \not\in x)$ then $x$ is satisfied by the empty set $\emptyset$ (and only the empty set).

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

Tell me if you object to that.

• JCummings says:

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