Coloring of subgraphs of G^n

Question

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?

Answer 1

This follows directly from the Hales-Jewett theorem.

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$.