Application of (infinite) Ramsey Theorem

Question

By Ramsey Theorem I mean the following statement: let $G$ be a countable complete graph whose edges are colored with a finite number of colors; then there is a subset $H \subseteq G$ such that the graph induced by $H$ is infinite, complete, and monochromatic.

I'd like to use Ramsey Theorem to prove the following: let $G$ be a countable complete graph whose edges are colored with a infinite number of colors. Assume further that there is $k < \omega$ such that every star (subgraph whose edges all share a common vertex) has at most $k$ colors. Then $G$ admits a complete and monochromatic infinite subgraph $H$.

My try is: identify $G$ with $\omega$ and consider the 'star of $0$'. In the star of $0$ there is an infinite set $H_0$ of the same color. Let $x_0$ be the minimum of $H_0$; in the star of $x_0$ there is an infinite set $H_1$ of the same color etc, etc. At the end I get a sequence of colors $c_0, c_1, \ldots$ Is there a way to conclude that there are only finitely many colors in this sequence?

Any help would be appreciated. Also, a completely different argument than mine is welcomed.

Answer 1

Let's define $H$ an infinite complete subgraph of $G$ as follows:

Start with any $v_0 \in V$, where $G=(V,E)$. Let $N(v_0):=\{v \in V: v_0 v \in E\}$ be the set of neighbours of $v_0$.

As $v_0$ and $N(v_0)$ can be seen as a star centered at $v_0$, there are at most $k$ colors in the edges between $v_0$ and $N(v_0)$. By the "infinite pigeonhole principle", there is a color $c_0$ and an infinite set $H_0 \subset N(v_0)$ such that the edges between $v_0$ and $H_0$ are all of colour $c_0$.

Now, suppose we are in the step $n$, that is, we already have vertices $v_0, \dots, v_n$ and $H_0 \supset \cdots \supset H_n$ such that for each $i$, the edges between $v_i$ and $H_i$ are all of color $c_i$ and $v_{i} \in H_{i-1}$.

We choose $v_{n+1} \in H_n$ and then, again by the "infinite pigeonhole principle", focusing on the star $(v_{n+1},H_n\setminus\{v_{n+1}\})$ we can find a colour $c_{n+1}$ and $H_{n+1} \subset H_n\setminus\{v_{n+1}\}$ such that the edges between $v_{n+1}$ and $H_{n+1}$ are all of colour $c_{n+1}.

Define $H$ the graph with vertices $\{v_n:n \in \mathbb{N}\}$ and edges $\{v_i v_j:i\neq j, i,j \in\mathbb{N}\}.$

Now let's show that the sequence $c_0,c_1,c_2,\dots$ has a finite number of colors.

Let $n_i$ be the first time a colour $c=c_{n_i}$ appeared in the sequence $(c_n)$, $i=0,1,2,\dots$. We will prove that, in fact, $(n_i)$ has at most $k$ terms.

See that $v_j \in N(v_{n_i})$ for every $j<n_i$ and there is at most $k$ colors in the star $(v_{n_i},N(v_{n_i}))$. So we only have $k-i$ choices for $c_{n_i}$, since $c_{n_i}\not \in \{c_{n_0},\dots,c_{n_{i-1}}\}$. That is, it is only possible to go on when, $k-i>0 \implies i<k$.

Finally, that means $(n_i)$ has at most $k$ terms and we can apply Ramsey Theorem on $H$ to find the monochromatic infinite complete subgraph of $H$ and, in particular, of $G$.