MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 14 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.