12
$\begingroup$

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

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, it is conjectured that for every coloring there is an antipodal pair of vertices, connected by a path that changes color at most once: http://theory.stanford.edu/~tomas/antipod.pdf

$\endgroup$
  • 2
    $\begingroup$ It is not true for $k=1.$ $\endgroup$ – Aaron Meyerowitz Nov 10 '14 at 7:05
  • $\begingroup$ Thank you, edited it to be $k>1$. When $k=1$ the torus structure does not help yet. $\endgroup$ – Daniel Soltész Nov 10 '14 at 14:21
  • $\begingroup$ Then I'd lean toward it being true. Consider for each point the closest thing which can not be reached in $k$ color changes. Maybe that would be effective. $\endgroup$ – Aaron Meyerowitz Nov 10 '14 at 14:50
  • $\begingroup$ Could you add a link to the hypercube problem? $\endgroup$ – domotorp Nov 10 '14 at 20:41
  • $\begingroup$ @domotorp Link added. I can also talk about the connections between the result of Feder and Subi, and this question. There is also an other paper of Leader and Long about the hypercube version. $\endgroup$ – Daniel Soltész Nov 10 '14 at 21:38
1
$\begingroup$

Definition: Consider the cycles of length $4$ in the torus. Let us call a subgraph of the torus a right-up diagonal if it consists of $2k$ such $4$-cycles, and the $i$-th cycle's up right corner is the $i+1$-st cycle's left-down corner. Every edge of the torus can be naturally double covered with right-up cycles. Let us call a path tight if it is contained in a right up diagonal.

We will prove slightly more.

Theorem: In every $2$-coloring of the torus graph, there is a tight path that changes colors at most $k-1$ times.

Proof:

Definition: We define the right-up diagonal of length $l$ similarly to the right up diagonal ($1 \leq l \leq 2k$), but there are only $l$ connected 4-cycles. The original right up diagonal (of length $2k$) is similar to a circle, but all the other shorter ones are similar to paths (or diagonal arcs as we are on a torus). Thus the diagonals of length $l$ have a natural beginning and endpoint, which coincides if the diagonal is of length $2k$.

Lemma: Consider all the right-up diagonals of length $l$ and all the left-up diagonals of length $l$. The average number of minimal color changes needed to get from the beginning to the endpoint of a diagonal, such that we can not leave the diagonal is at most $l$.

Proof: Consider a $4$-cycle. There is a right-up and a left-up diagonal containing this cycle. If (WLOG) at the right-up diagonal we have to change colors twice in this cycle, it must happened this way: We arrived to the bottom left vertex of the cycle with our path having (WLOG) the color blue. Both edges adjacent to this vertex and belonging to this cycle were red, and the other two edges blue. Thus the left-up diagonal containing this cycle does not have to change colors at this cycle, as there is a red and a blue monochromatic path between the bottom right and the top left vertices. Thus on the average a single $4$-cycle can not cause more than $1$ color change. $ \square $

Corrolary: As in a diagonal of length $k$, the beginning and endpoints of the diagonal are antipodal. We have that the average number of necessary color changes from a point to its antipodal pair using only tight paths is at most $k$. (Actually when we averaged, we took into account all the four possible diagonals connecting these points, and the best tight path in every such diagonal.)

So we will have such a path with only $k-1$ color changes unless the average is exactly $k$ and every such path with minimal color changes has to change colors exactly $k$ times. Consider now diagonals of length $2k$. By the lemma we have that the average number of paths with minimal number of color changes from the beginning to the endpoint (which is the same point) is at most $2k$ (not counting that maybe we arrive with a different color when we close the cycle). but every diagonal of length $2k$ is the union of two diagonals of length $k$ where we have that we need $k$ color changes. Thus if the average number of color changes is $2k$ but we always need at least $2k$ changes, we conclude that in every right-up and every left-up diagonal, there is a $2k$ cycle that changes colors exactly $2k$ times. (now we can count all the color changes, as after an even number of color changes, in the end we always arrive with the starting color)

Now we will work with these cycles.

Definition: Let us call a vertex in a right-up diagonal subgraph central, if every cycle of length $2k$ in this subgraph, passes through this vertex. There are $2k$ central and $4k$ non central vertices in every right-up diagonal of length $2k$. Every vertex is central in precisely one right-up diagonal of length $2k$.

Consider a right up diagonal of length $2k$ and the associated cycle with $2k$ color changes. If such a cycle has a color change at a central vertex, we have a path along this cycle to the antipodal pair of this vertex with at most $k-1$ changes. Thus we can assume that every such cycle has its color changes at non-central points. But then the cycles have to change its color at every non-central point as there are $2k$ color changes. Thus if there are antipodal non-central points on this cycle, we have exactly $k-1$ color changes between them.

The only case left to examine is when we have such a cycle, and every non-central point on the cycle is such that its antipodal pair is not on the cycle. We could change the cycle along a $4$-cycle of the right-up diagonal. (As every $4$-cycle has two common edges with our $2k$ cycle and two other edges.) So if we change the cycle this way and the number of color changes is still $2k$, we are done.

If for every $4$-cycle we can not change our cycle without increasing the number of color changes, we will conclude that every $4$-cycle is colored properly (adjacent edges have different colors): Let C_4 be a $4$-cycle on a right-up diagonal. The associated cycle with $2k$ color changes shares exactly two edges with this cycle. At the associated cycle, there are no color changes at the central vertices, and there is always a color change at non-central vertices. Thus the change of the cycle along this $4$-cycle increases the number of color changes, the $4$-cycle had to be colored properly. (draw a nice picture)

There is only one coloring where every $4$-cycle is colored properly, and at this coloring it is easy to find tight paths connecting antipodal vertices. $\square$

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.