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

Advertisements

About Jay Cummings

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.

          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.

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s