Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most $k-1$ times? Edit: $k>1$ as pointed out in the comments.
More formally: The $2k \times 2k$ grid graph on a torus is defined as follows. $$V(G):=\{(i,j)|i,j\in [1,2k]\cap\mathbb{Z} \}$$ Two vertices are connected if and only if on one of the coordinates they coincide, and on the other one, their values differ by exactly one, modulo $2k$.
![torus][1] [1]: https://i.sstatic.net/F7p0y.jpg
We say that a pair of vertices is antipodal if their distance is maximal. Equivalently if both their coordinates differ by $k$, modulo $2k$. The path between them which we require to change colors only $k-1$ times is not required to be $2k$ long.
Additional information:The interesting part of the question is that the pairs are $2k$ away, but we only have $k-1$ color changes. If true, sometimes we need $k-1$ color changes, as the following coloring shows:
- Color the edges $((i,j),(i+1,j))$ red if $i$ is even, and blue otherwise.
- Color the edges $((i,j),(i,j+1))$ red if $j$ is even, and blue otherwise.
There is a similar open problem in the hypercube. There, but there it is conjectured that for every coloring there is an antipodal pair of vertices, connected by a singlepath that changes color change suffices.at most once: http://theory.stanford.edu/~tomas/antipod.pdf