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

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.