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

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?

share|cite|improve this question
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
up vote 4 down vote accepted

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

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.