# Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , \overline{r}=(r_1,...,r_n) \in R^n$ and for each $1 \le i \le n : (l_i,r_i)\in E\},$ and $G^{(n)}=(L^n,R^n,E^{(n)}).$

I want to show that for any number of colors $c>0$ exists an $n\in\mathbb{N}$ such that $G^{(n)} \mapsto (G)^2 _c$.

I thought about counting all the full sub-graphs of $G^{(n)}$ which are isomorphic to $G$ and then showing that there must be at least one full sub-graph whose edges are single colored, but I got a bit tangled doing so, which made me think there should be an easier way to do so. Am I on the right path or is there actually a more convenient way to prove this?

-
What is a bigraph? What does $G^{(n)}\mapsto(G)^2_c$ mean? – bof Dec 6 '13 at 11:06
I meant $G$ is a bipartite graph, i.e. a graph such that it's vertices can be divided into two groups: left and right, so that every edge in the graph is between a vertex from the right and one from the left. by $G^{(n)} \mapsto (G)^2 _c$ I meant that for every coloring $\varphi$ of edges from $G^{(n)}$ in $c$ colors, there is a full sub-graph of $G^{(n)}$ which is isomorphic to the original $G$. – Roman Vale Dec 6 '13 at 14:58

Observe that $E^{(n)}$ is isomorphic to $E^n$, the cartesian product of the edge set of $G$. A $c$-colouring of the edges of $G^{(n)}$ is then naturally a $c$-colouring of $E^n$, so, if $n$ is sufficiently large, then by the Hales-Jewett theorem there is a monochromatic combinatorial line in $E^n$. But a line is precisely an isomorphic copy of $G$.
This is best illustrated by an example. Take $L=\{l,m\}$, $R = \{r,s\}$ and let $G$ be the path $lrms$. A line in $E^5$ might look like $$(\star, \star, (l,r), (m,r), (m,s)) \equiv ((*,*,l,m,m),(\dagger, \dagger,r,r,s)),$$ where the $\star\equiv(*,\dagger)$'s mark the active coordinates and range over $E = \{(l,r), (m,r), (m,s)\}$. We obtain a corresponding isomorphic copy of $G$ by separating the factors on the right-hand side and allowing $*$ to range over $L$ and $\dagger$ to range over $R$ independently. So for our example the tuples $(l,l,l,m,m)$ and $(m,m,l,m,m)$ in $L^5$, and $(r,r,r,r,s)$ and $(s,s,r,r,s)$ in $R^5$ induce an isomorphic copy of $G$.