On unabridged versions of Ramsey’s theorem

In continuation of our discussions on Ramsey theory in this post we plan to prove the unabridged versions of Ramsey’s theorem. While the abridged versions dealt with graphs, unabridged versions deals with hypergraphs. A hypergraph, is a set of vertices V together with a set of subsets of V of a fixed order n. If n=2 then we get back the ordinary definition of a graph.

An example of a hypergraph of order 3 is given below:

The vertex set V=\{a,b,c,d,e\} and the hyperedges are given by: \{a,b,c\}, \{b,d,e\} and \{a,b,d\}.

The infinite unabridged version of Ramsey’s theorem may now be described as follows: Given a complete infinite hypergraph of order n with vertex set \mathbb{N}, and a r-coloring of its hyperedges we are guaranteed a infinite complete monochromatic subgraph.

Let us try to express this more succinctly. We will extend the previously defined arrows notation as follows: The notation \alpha\rightarrow (\beta)^n_r will mean that every r-colored complete hypergraph of order n on \alpha vertices contains a monochromatic complete subgraph with \beta vertices. Since hypergraphs do not seem to be as picturesque as graphs, so maybe the idea will be better expressed in terms of sets: \alpha\rightarrow (\beta)^n_r equivalently means that for any assignment of r-colors to the n-subsets of \alpha, there is a particular color (say red) and a subset X of \alpha of size \beta such that all n-subsets of X are red. (Note that \alpha,\beta etc can be any cardinal numbers.)

With the notation that \omega stands for the cardinality of \mathbb{N} the infinite version of Ramsey’s theorem now is:

Theorem: \forall n,r\in\mathbb{N}, \omega\rightarrow(\omega)^n_r.

The proof is essentially on the same lines as in the abridged case, with the addition that we induct on n. (n may intuitively be thought of as the “hyper-ness” of our hypergraph.)

Proof: By induction on n. If n=1 we just get the infinite pigeonhole principle: Any finite partitioning of \mathbb{N} contains an infinite part. Indeed, both the infinite and finite Ramsey theorems may be thought of as gigantic generalizations of the pigeonhole principle.

Now suppose that for a fixed n,r we have \omega\rightarrow(\omega)^n_r. Now consider any r-coloring f of the n+1-subsets of \omega. Just like in the proof of the abridged case we build a sequence (w_k). In the abridged case we applied the infinite pigeonhole principle repeatedly at this point. Here we will use the induction hypothesis repeatedly. Let w_1=1. Consider the r-coloring f_{w_1} of all n-subsets of \omega-\{1\} given by f_{w_1}(X)=f(\{1\}\cup X). By the induction hypothesis there will be a countable subset of \omega whose all n-subsets will be monochromatic. Call that subset V_1. Let the least element of V_1 be designated as w_2.

The construction of (w_k) follows by induction: If the set V_k and its least element w_{k+1} have been found, consider the r-coloring f_{w_{k+1}} of the n-subsets of V_k given by f_{w_{k+1}}(X)=f(\{w_{k+1}\}\cup X). By the induction hypothesis it contains a countable set all of whose n-subsets are monochromatic. Call that subset V_{k+1}. Its least element is designated as w_{k+2}.

The sequence (w_k) has the property that given any w_i the union of \{w_i\} with any n-order subset containing elements from w_{i+1},w_{i+2},w_{i+3}\cdots has the same color (with respect to the the original coloring f). Let us call w_i as c_j-based if this color is c_j. The fact that all the members of the sequence (w_k) are based in any of r-ways induces a partitioning of the sequence (w_k). By the infinite pigeonhole principle we are guaranteed an infinite part. Now, by ordering the terms appropriately in this infinite part we have a subsequence (w_{k_j}) of (w_k) in which all vertices are the same color base, say c_1. It is now easy to observe that all the n+1-subsets of this infinite part are colored c_1, which proves the theorem.\Box

We now turn to the finite version. In our arrows notation, the natural generalization from the abridged analogue reads:

Theorem: \forall l,n,r\in\mathbb{N}, \exists m\in\mathbb{N} such that m\rightarrow (l)_r^n.

Proof: The proof is identical to the abridged case with cosmetic changes. By way of contradiction assume that there is an l such that for all m\in\mathbb{N} we have m\nrightarrow (l)_r^n. We will use the notation \hat{K_i} for a hypergraph on i vertices where all possible n-subsets of the vertices are the hyperedges. Also let G be a hypergraph with vertices V=\{v_i:i\in\mathbb{N}\} and let the hyperedges of G be enumerated by E=\{E_i:E_i\subset\mathbb{N}, |E_i|=n\}. We construct a (rooted) tree T as follows:

1. First introduce a root vertex rt.

2. Each vertex is allowed to have at most r children which correspond to the r-colors, subject to it satisfying the criteria below. A child is always labeled by one among the r-colors. (Call the colors c_1,c_2\cdots c_r for convenience).

3. A child c_i is permitted if and only if its introduction creates a path of some finite length k starting from the root, so that if the hyperedges E_1,E_2\cdots E_k are colored by the colors used in the path in the same order, then the corresponding subgraph in G does not contain a monochromatic \hat{K_l}. For example if the introduction of a child c_i creates the k length path rt,c_a,c_b\cdots ,c_i and the hyperedges E_1,E_2,\cdots E_k when colored c_a,c_b\cdots c_i don’t contain a monochromatic \hat{K_l} the child c_i is permitted to be added to T.

Note that for all m, there always exists a coloring of \hat{K_m} such that no monochromatic \hat{K_l} exists within. So the situation that a child cannot be added to any vertex at a given level k cannot arise. For we can always take a coloring of \hat{K_{k+n}} containing no monochromatic \hat{K_l}. Since any k hyperedges in it would yield a sequence of colors already existing in T, we know which vertex to add the child to. We give the child the color corresponding to any other edge. Hence we can forever keep adding children and so T is infinite. It is also obvious that each level k of T has at most r^k vertices and so each level is finite.

Now by Konig’s lemma there will be an infinite path in T. This infinite path provides a r-coloring of G that contains no monochromatic \hat{K_i} and hence no monochromatic infinite hypergraph which contradicts the infinite Ramsey theorem proved above. This contradiction proves the theorem.\Box

The astute reader may have noted that we have used weak versions of the axiom of choice occasionally in the proof. Ramsey himself was aware of this and remarked so in his original paper. In fact, it can be proved that Ramsey’s theorem cannot ever be proved without using some form of the axiom of choice. Moreover it can be shown that a weak form of the axiom of choice is equivalent to Ramsey’s theorem. Hence Ramsey’s theorem may be interpreted as a choice axiom.

Advertisements

1 Comment

Filed under Combinatorics, Graph theory, Ramsey theory

One response to “On unabridged versions of Ramsey’s theorem

  1. Pingback: Ramsey infinite | Questionhypoth

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