Ramsey's theorem of complete bipartite graph

349 Views Asked by At

Is there an easy way to deduce Ramsey's theorem of complete bipartite graph from the original Ramsey's theorem (including the hypergraph version)?

Ramsey's theorem of complete bipartite graph (the most basic version) states:

For every $m$ there exists $N$ such that every edge coloring $\chi:E[K_{N,N}]\to [r]$ contains a monochromatic subgraph $K_{m,m}$.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $r,m$ be given. By Ramsey's theorem there is a number $N$ such that every coloring $E(K_N)\to[r]$ contains a monochromatic $K_{2m}$.

I claim that any coloring $c:E(K_{N,N})\to[r]$ contains a monochromatic $K_{m,m}$.

Let the vertex sets of $K_{N,N}$ be $\{x_1,\dots,x_N\}$ and $\{y_1,\dots,y_N\}$. Consider $K_N$ with vertex set $[N]$. Define a coloring $\hat c:E(K_N)\to[r]$ so that, if $i,j\in N$ and $i\lt j$, then $\hat c(\{i,j\})=c(x_i,y_j)$. Let $i_1\lt i_2\lt\cdots\lt i_m\lt j_1\lt\cdots\lt j_m$ be such that $\{i_1,\dots,i_m,j_1,\dots,j_m\}$ induces a monochromatic $K_{2m}$ in $K_N$. Then $\{x_{i_1},\dots,x_{i_m}\}\cup\{y_{j_1},\dots,y_{j_m}\}$ induces a monochromatic $K_{m,m}$ in $K_{N,N}$.