Ramsey Theory, monochromatic subgraphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T04:17:39Z http://mathoverflow.net/feeds/question/6447 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6447/ramsey-theory-monochromatic-subgraphs Ramsey Theory, monochromatic subgraphs alext87 2009-11-22T09:32:59Z 2009-11-22T18:44:48Z <p>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. </p> http://mathoverflow.net/questions/6447/ramsey-theory-monochromatic-subgraphs/6452#6452 Answer by Konstantin Slutsky for Ramsey Theory, monochromatic subgraphs Konstantin Slutsky 2009-11-22T09:59:52Z 2009-11-22T09:59:52Z <p>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.</p> http://mathoverflow.net/questions/6447/ramsey-theory-monochromatic-subgraphs/6472#6472 Answer by gowers for Ramsey Theory, monochromatic subgraphs gowers 2009-11-22T18:44:48Z 2009-11-22T18:44:48Z <p>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&lt; 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&lt; 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.</p>