Ramsey Theory, monochromatic subgraphs - MathOverflow

Ramsey Theory, monochromatic subgraphs

2009-11-22T09:32:59Z

If we have the complete countably infinite bipartite graph $K_{\omega,\omega}$ and we colour the edges with just two colours. Should we expect to get a monochromatic copy of $K_{\omega,\omega}$. Infinite Ramsey theorem gives us infinitely many edges of one colour but this is no enough.

Answer by Konstantin Slutsky for Ramsey Theory, monochromatic subgraphs

2009-11-22T09:59:52Z

I think the answer is NO in general. Consider the following example. Color edge between vertexes $(m,n)$, where $m$ comes form one copy of $\omega$ and $n$ from the other, into red if $m$ is less than $n$ and into blue otherwise. Then there is no monochromatic copy of complete countably infinite bipartite graph.

Answer by gowers for Ramsey Theory, monochromatic subgraphs

2009-11-22T18:44:48Z

The example given by Konstantin Slutsky is, however, essentially unique, in the following sense. Let $G$ be the complete bipartite graph with both vertex sets equal to (copies of) $\mathbb{N}$ and colour its edges red or blue. For each $m< n$, colour the set ${m,n}$ according to whether the edge $(m,n)$ is red or blue and whether the edge $(n,m)$ is red or blue. (So this is a 4-colouring of the complete graph on $\mathbb{N}$.) By Ramsey's theorem we can find a subset $X$ of $\mathbb{N}$ such that all pairs ${m,n}$ with $m,n\in X$ have the same colour. If the colour is RED-RED or BLUE-BLUE then we have a monochromatic bipartite subgraph by choosing two disjoint subsets $Y$ and $Z$ of $X$ (to avoid the problem when $m=n$). If the colour is RED-BLUE then we can again pass to two disjoint subsets, which we could even make alternate, and the edge $(m,n)$ will then be RED if $m< n$ and BLUE if $m> n$, and similarly if the colour is BLUE-RED. So we either find a monochromatic subgraph or we find Konstantin Slutsky's example. This is an example of a "canonical Ramsey theorem" -- you can't find a monochromatic structure but you can find a simple "canonical" structure.