Tag Archives: pigeonhole principle

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

Konig’s lemma

This post is about trees. Not real-life ones but mathematical trees, or more formally about acyclic connected graphs. Just as actual big skinny trees are tall, graph theoretic big skinny trees are also tall. The goal here is to prove this formally.

But first some definitions. A tree is called labeled if every vertex has been assigned a symbol, called its label. A fixed vertex in a tree may be labelled as r and referred to as its root. The level i in a tree is the collection of all vertices at a fixed distance i from the root. Admittedly these definitions are informal and may be formalized in terms of directed graphs.

An example of a labelled tree is given below:

Here r is the root and the vertex sets \{a,b\} and \{1,2,3\} are at level 1 and 2 respectively. Clearly this labeling is arbitrary and any other labeling is also possible.

We now prove our result. It is due to Konig, a Hungarian professor of mathematics, who had Erdos amongst his students. It is called a lemma because it was initially used by Konig to investigate another theorem (see this) . As often happens it has turned out to be a powerful tool to use on many other problems as well.

Lemma: If T is an infinite tree and each level of T is finite then T contains an infinite path.

Proof: Suppose T is a labeled tree with root r. Let L_0=\{r\}, L_1,L_2,\cdots be the levels of T. We construct our path by starting with r. Next we partition all vertices in levels higher then L_0 (i.e. all vertices in levels L_i where i>0) into as many finite parts as is the cardinality of L_1. In other words if L_1=\{v_1,\cdots v_n\} then we partition the vertices (there are infinitely many of them) in n parts: P_1,P_2\cdots P_n. This partitioning is done as follows: Any vertex w will be connected to r via some v_i owing to connectedness. We put w in P_i.

Now since we have partitioned infinitely many vertices in finitely many parts, one of the parts will contain infinitely many vertices.(This is also called the infinite pigeonhole principle). Let that part be P_j. Choose w_1=v_j as the next vertex in our under-construction path. Next we delete the vertex r and consider the component containing w_1. It is also an infinite tree with each level finite and having w_1 as its root. By a similar piece of reasoning, we get a vertex w_2 which is adjacent to w_1 and has infinitely many vertices corresponding to it. We continue building our path by choosing w_2 as a part of it. By induction we can continue and get an infinite path rw_1w_2\cdots. This proves the theorem.\Box

It should be noted that at each of the infinitely many stages of selecting the w_i we choose it out of a finite set: the finite set of vertices at that level each of which correspond to infinite parts in the current partitioning. There is no canonical way to make this choice. To ensure that this can be done we need to use a weak form of the axiom of choice: Let X\ne\emptyset and \mathcal{F}(X) be the collection of all finite subsets of it. Then there is a function f:\mathcal{F}(X)-\emptyset\to X such that f(x)\in x\forall x\in \mathcal{F}(X)-\emptyset. A curious fact is that Konig’s lemma in turn applies this weak form of the axiom of choice and so both of them are equivalent. While their equivalence can be established using the ZF axioms, obviously neither can be proved within ZF.

3 Comments

Filed under Combinatorics, Graph theory