Deduce the finite Ramsey theorem from the infinite case.

228 Views Asked by At

I'd like to ask for some checking of my proof for the statement below.

Using the fact that every $\textbf{red/blue}$ colouring of $\mathbb{N} \choose 2$ contains an infinite monochromatic clique, show that for every positive integer $t \geq 2$, there exists a finite $n$ such that every $\textbf{red/blue}$ colouring of $E(K_n)$ contains a monochromatic $K_t$.

My proof is in fact a modification of the proof below, which uses right-monochromatic vertex sequence as its main tool.

enter image description here

The same procedure is used in the proof for infinite Ramsey number.

enter image description here

My proof:

Consider an arbitrary 2-colouring of $\mathbb{N} \choose 2$, and let $v_i, i \in \mathbb{N}$ be the vertices. If we try to apply the process in the proof of Claim 2.3. an infinite number of times, as in the proof of Theorem 2.6, but only restrict ourselves to some of the first steps of the procedure, we're bound to arrive at the value $t$ before getting our infinite monochromatic clique.

The details of the procedure is as follows. Let $\{w_1, w_2,..., w_{2t-2}\} \subset \{v_i, i \in \mathbb{N}\}$ be the right-monochromatic vertex sequence that we will eventually obtain. Set $w_1 = v_1, \text{and } S_0 = \{v_i | i \in \mathbb{N}\}$.

Consider the edges from $v_1$ to other $v_i$'s. If either red or blue occurs a finite number of times, then the other colour must occur an infinite number of times, and we set $S_1$ to be the set of vertices of the latter type. Otherwise, both red and blue must occur an infinite number of times, and we choose $S_1$ to be the set of vertices corresponding to either colour.

Given a set $S_i$, then, we set $w_{i+1}$ to be the vertex $v_k \in S_i$ with the lowest index $k$. We consider the edges from $v_k$ to the vertices $v_m \in S_i, \text{with } m > k$, and carry out the same analysis as above, setting $S_{i+1} \subset S_i \setminus \{v_k\}$ to be the set of vertices corresponding to the infinitely-occurring colour.

We note that the sequence $\{w_1,..., w_{2t-2}\}$ constructed this way is indeed right-monochromatic. Once this sequence is obtained, applying the pigeonhole principle on the first $2t - 3$ vertices gives a monochromatic complete graph on $\left\lceil \frac{2t-3}{2} \right\rceil = t-1$, which, together with the last vertex $w_{2t-2}$, forms a monochromatic $K_t$.

The integer $n$ that we're interested in is the index of the vertex $v_n$ such that $w_{2t-2} = v_n$.