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 together with a set of subsets of of a fixed order . If then we get back the ordinary definition of a graph.
The vertex set and the hyperedges are given by: , and .
The infinite unabridged version of Ramsey’s theorem may now be described as follows: Given a complete infinite hypergraph of order with vertex set , and a -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 will mean that every -colored complete hypergraph of order on vertices contains a monochromatic complete subgraph with vertices. Since hypergraphs do not seem to be as picturesque as graphs, so maybe the idea will be better expressed in terms of sets: equivalently means that for any assignment of -colors to the -subsets of , there is a particular color (say red) and a subset of of size such that all -subsets of are red. (Note that etc can be any cardinal numbers.)
With the notation that stands for the cardinality of the infinite version of Ramsey’s theorem now is:
The proof is essentially on the same lines as in the abridged case, with the addition that we induct on . ( may intuitively be thought of as the “hyper-ness” of our hypergraph.)
Proof: By induction on . If we just get the infinite pigeonhole principle: Any finite partitioning of 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 we have . Now consider any -coloring of the -subsets of . Just like in the proof of the abridged case we build a sequence . In the abridged case we applied the infinite pigeonhole principle repeatedly at this point. Here we will use the induction hypothesis repeatedly. Let . Consider the -coloring of all -subsets of given by . By the induction hypothesis there will be a countable subset of whose all -subsets will be monochromatic. Call that subset . Let the least element of be designated as .
The construction of follows by induction: If the set and its least element have been found, consider the -coloring of the -subsets of given by . By the induction hypothesis it contains a countable set all of whose -subsets are monochromatic. Call that subset . Its least element is designated as .
The sequence has the property that given any the union of with any -order subset containing elements from has the same color (with respect to the the original coloring ). Let us call as -based if this color is . The fact that all the members of the sequence are based in any of -ways induces a partitioning of the sequence . 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 of in which all vertices are the same color base, say . It is now easy to observe that all the -subsets of this infinite part are colored , which proves the theorem.
We now turn to the finite version. In our arrows notation, the natural generalization from the abridged analogue reads:
Theorem: such that .
Proof: The proof is identical to the abridged case with cosmetic changes. By way of contradiction assume that there is an such that for all we have . We will use the notation for a hypergraph on vertices where all possible -subsets of the vertices are the hyperedges. Also let be a hypergraph with vertices and let the hyperedges of be enumerated by . We construct a (rooted) tree as follows:
1. First introduce a root vertex .
2. Each vertex is allowed to have at most children which correspond to the -colors, subject to it satisfying the criteria below. A child is always labeled by one among the -colors. (Call the colors for convenience).
3. A child is permitted if and only if its introduction creates a path of some finite length starting from the root, so that if the hyperedges are colored by the colors used in the path in the same order, then the corresponding subgraph in does not contain a monochromatic . For example if the introduction of a child creates the length path and the hyperedges when colored don’t contain a monochromatic the child is permitted to be added to .
Note that for all , there always exists a coloring of such that no monochromatic exists within. So the situation that a child cannot be added to any vertex at a given level cannot arise. For we can always take a coloring of containing no monochromatic . Since any hyperedges in it would yield a sequence of colors already existing in , 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 is infinite. It is also obvious that each level of has at most vertices and so each level is finite.
Now by Konig’s lemma there will be an infinite path in . This infinite path provides a -coloring of that contains no monochromatic and hence no monochromatic infinite hypergraph which contradicts the infinite Ramsey theorem proved above. This contradiction proves the theorem.
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.