Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL

Suppose the algorithm discovered two walks of same length $W_1=(u_1,v_1)$, $W_2=(u_2,v_2)$ such that $|p(W_1)-p(W_2)|\ge 4T+5$. Without loss of generality, let $p(W_1)=K$ and $p(W_2)=K+\epsilon (4T+5)$ with $\epsilon \in \{1,-1\}$. The adversary then reveals that $W_1$ and $W_2$ are aligned at distance exactly $2T+2$. By Lemma 3 the cycle $C$ defined by $(u_1,v_1,v_2,u_2,u_1)$ must have potential $0$:

and thus $p((v_1,v_2))+p((u_2,u_1))=\epsilon (4T+5)$. However, $|p(u_2,u_1)|=|p(v_1,v_2)|=2T+2$, so $|p((v_1,v_2))|$ and $|p((u_2,u_1))|$ are at most $2T+2$, a contradiction. $◀$

With the above observation in place, we can improve the strategy of Lemma 5 to give us nearly linear potential difference along a row.

Using the same adversarial strategy as in Lemma 5, build a path $W$ with potential increase $9T$ and at most $2^{10T}$ length. This is possible for large enough values of $T$ (and $n$). Because of Lemma 6, any parallel path $W^{\prime }$ satisfying its conditions must have potential between $5T-4$ and $13T+4$. Moreover, if we split a row into $m$ consecutive segments of length $|W|$, the potential of the whole row is between $m(5T-4)$ and $m(13T+4)$. Hence, we can force paths of length $N=\omega (2^{10T})$ such that any of its subpaths $W^{\prime }$ of length at least $|W|\le 2^{10T}$ has potential increase at least $c|W^{\prime }|$ with $c=4T/|W|\ge 4T/2^{10T}$. $◀$

Let $T=(1/100)\log n$. Without restriction, we consider only the case where $\theta \in [0,\pi /4]$. The construction for the general case is obtained by applying reflections along the horizontal and vertical axis or by swapping the two.

As in Lemma 5, our strategy is based on incrementally building self-similar objects while driving the potential difference up by at least one unit at every level. From one level to the next, the size of the construction should increase by only a multiplicative constant factor. Indeed, similar to Lemma 5, the construction at level $j+1$ is obtained by creating two copies of it at level $j$ and adequately placing them relative to each other.

The construction at level $0$ consists of a single node. Higher levels of the construction are shaped as the objects already mentioned in the statement of the lemma, namely parallelograms where two sides are vertical and of length equal to one plus the current level of the construction $j\le k$ and the two other sides have angle $\theta$ relative to the horizontal axis.

To simplify the description, we use the term $(j,\theta )$-parallelogram to refer to such parallelograms. Given such a parallelogram $P$, we call the node of $P$ with minimal coordinates (in lexicographic order) the anchor node of $P$. (Note node here refers to nodes of $G$ in the embedding $\tilde{G}$, not points on the plane.) We guarantee through the construction that every $(j,\theta )$-parallelogram has the same height $j+1$ and width $w_j$ and that these are both integral. These technical details are somewhat tedious but needed to ensure we reach the desired height for the construction.

Let us describe the construction inductively (see also Figure 3). To obtain a parallelogram at level $j+1$ from two $(j,\theta )$-parallelograms $P_1$ and $P_2$ at level $j$, we proceed as follows:

1. 1.

   Let $u_1$ and $u_2$ be the anchor nodes of $P_1$ and $P_2$, respectively.

2. 2.

   Set $i=w_j+2T+2$. Note that, since we assumed $\theta \in [0,\pi /4]$, this implies both $D_{-}(u_1,i)$ and $D_{+}(u_1,i)$ are at distance greater than $2T+1$ but still at most $O(T)$ from $P_1$.

3. 3.

   Place $P_2$ relative to $P_1$ by placing $u_2$ on top of $D_{-}(u_1,i)$ or $D_{+}(u_1,i)$, whichever of the two choices guarantees that the maximal potential difference increases by at least one unit. (This choice is made using the same reasoning as in the setting of Lemma 5.)

4. 4.

   Recall $P_1$ and $P_2$ both have height $j+1$. Hence, if we could place $P_2$ on $D(u_1,i)$ (the ideal point to follow the slope $\theta$), then we would be actually able to fit both $P_1$ and $P_2$ in a $(j,\theta )$-parallelogram perfectly. Since both points $D_{-}(u_1,i)$ and $D_{+}(u_1,i)$ are at most unit distance from $D(u_1,i)$, it follows that there is a $(j+1,\theta )$-parallelogram $P$ containing both $P_1$ and both the placement choices for $P_2$. (In particular, this implies the shape of the $(j+1,\theta )$-parallelogram at the next level of the construction is uniquely defined.)

5. 5.

   Once $P$ is fixed, reveal all nodes inside it that have not been revealed previously, thus reaching the next level of the construction.

Note the choice of placement for $P_1$ and $P_2$ ensures the relative position of the two is kept hidden from the algorithm until both $P_1$ and $P_2$ have been completely labeled. The argument for the increase in potential difference is the same as in Lemma 5.

Due to the relative placement of $P_1$ and $P_2$, it is evident that we can guarantee the height and width guarantees mentioned previously. One technical issue concerns the construction at level $1$: There it is needed that the parallelograms have height $2$ as otherwise it might be that there is no path of $\tilde{G}$ that is fully contained within it. This is required so that the potential difference is defined between any two nodes in the same parallelogram (and also the sole reason why we only obtain height $k+1$ and not $k$ in the statement).

Finally, we verify the size of the construction allows us to reach the desired level $j=k$: Clearly, we have $w_{j+1}=2(w_j+T+1)$. Since $w_0=0$, by solving the recursion, we obtain $w_k=2(2^k-1)(T+1)$. As the final parallelograms have height $k+1$, we need thus at most $O(Tk)\cdot 2^k=n^{o(1)}$ nodes for the construction. $◀$

Our argument is independent of the actual orientation of the edges of the grid and only cares about the direction in which the potential is increasing or decreasing. For this reason, we can assume that we are always forcing the algorithm to increase or decrease the potential in one specific direction. This is because, if this is not the case, we could go through the same construction by virtually flipping the orientation. For example, if we want the potential to increase from west to east but the algorithm is making it decrease, in our construction we can consider west to be east and west to be east. Thus, w.l.o.g. in the following argument, we consider the potential to be always increasing from west to east and decreasing from south to north.

Acting as the adversary, we start from a node $w_1$ and we reveal nodes to the algorithm belonging to the same row of $w_1$, going neighbor by neighbor always from west to east. Let the path revealed this way be $W_1=(w_1,w_2,\mathrm{\dots },w_i)$. Thanks to Lemma 7, the algorithm is forced to nearly linearly increase the potential along this row. Now consider the node $w_i$. We reveal nodes to the algorithm that belong to the same column of $w_i$, going neighbor by neighbor always from south to north. Let the path revealed this way be $W_2=(w_i,w_{i+1},\mathrm{\dots },w_j)$. Applying the same reasoning as in the proofs of Lemma 6 and Lemma 7, the algorithm linearly decreases the potential along this column. Notice that we can choose $W_2$ to be long enough so that $p(W_1)+p(W_2)=0$. Let $|p(W_1)|=c_1(T)|U_1|$ and $|p(W_2)|=c_2(T)|W_2|$, where $c_1$ and $c_2$ are functions defined as in the statement of Lemma 7. Let $c(T)=\frac{c_1(T)}{c_2(T)}$ be such that $|W_2|=c(T)|W_1|$. From Lemma 4 we know that $c_1(T)\le \frac{1}{3}$, and Lemma 7 guarantees that $c_2(T)\ge \frac{1}{2^{O(T)}}$, thus $c(T)\le \frac{2^{O(T)}}{3}$. This implies that, if we choose $|W_1|=O(2^{100T})$ so that we satisfy the lemma statement, we always have enough room to grow $W_2$ so that we satisfy condition $p(W_1)+p(W_2)=0$, and this is because $|W_2|=c(T)|W_1|\le \frac{2^{O(T)}}{3}|W_1|$. Moreover, we can always swap the roles of $W_1$ and $W_2$ after their construction, and thus also guarantee that $|W_1|\ge |W_2|$. Finally, we remark that $|W_1|+|W_2|\le 2^{O(T)}\cdot 2^{100T}=2^{O(T)}$. We conclude by observing that $W=(w_1,w_2,\mathrm{\dots },w_i,w_{i+1},\mathrm{\dots },w_j)$ is an $L$-path that satisfies the statement of the lemma by taking $u=w_1$ and $v=w_j$. $◀$

The adversary reveals an L-path $W$ from node $u$ to node $v$ following the strategy in Lemma 11 such that one of the arms of the L-path has length at least $2^{100T}$ and forcing the algorithm to color it in such a way that $p(W)=0$. It then reveals to the algorithm a diagonal-path $D_{u,v}$ from node $u$ to node $v$. In order to prove a certain property about $D_{u,v}$, we need the following two simple analytical observations.

We may assume that $f(0)>k$ and as otherwise we could pick either $x=0$ or $x=b$. Let be the largest integer such that $f(a)>k$. Now $f(a+1)$ is either in range $[-k,k]$ or it is . In the former case we are done and can pick $x=a+1$. In the latter case $|f(a+1)-f(a)|\ge 2k$, which contradicts our assumption. $◀$

If $g(0)=0$, we are done. W.l.o.g. assume $g(0)>0$ as otherwise we consider the function $-f$. We show there exists $x\in {[0,b-\mathrm{\ell }]}_{\mathbb{Z}}$ such that $g(x)\le 0$; by Lemma 12 this then implies the claim as $g$ varies by at most $2k$ between consecutive indices.

Assume for contradiction that $g(x)>0$ for all $x\in {[0,b-\mathrm{\ell }]}_{\mathbb{Z}}$. Indeed, we may even assume that $g(x)>2k$ everywhere as otherwise we could pick $x$ where this does not hold. Consider now the function $f$ under this assumption. The first few values of $f$ are $f(0)=0$, $f(\mathrm{\ell })>2k$, $f(2\mathrm{\ell })>4k$, and so on since $g(x)>2k$ everywhere, which forces $f$ to increase. At the same time, $f$ can decrease under the assumption that the difference between consecutive indices of $f$ is at most $k$. Hence, we have $f({\mathrm{\ell }}^2)>2kl$, $f({\mathrm{\ell }}^2+1)>2k\mathrm{\ell }-k$, $f({\mathrm{\ell }}^2+2)>2k\mathrm{\ell }-2k$, and so on, until finally $f({\mathrm{\ell }}^2+\mathrm{\ell }-1)>2k\mathrm{\ell }-k(\mathrm{\ell }-1)>0$ and $f({\mathrm{\ell }}^2+\mathrm{\ell })>2k^2+2k$. Thus, for every $x\ge {\mathrm{\ell }}^2$, the function $f$ never reaches a non-positive value, contradicting $f(b)=0$. $◀$

With these technicalities in place, we now prove that we can find two nodes in $D_{u,v}$ with constant potential difference between them.

Let $u=(\alpha ,\beta )$ and $v=({\alpha }^{\prime },{\beta }^{\prime })$ and let $W_{\text{row}}$ denote the row sub-path of $W$ and set $B≔|W_{\text{row}}|$. By the construction of the L-path ( Lemma 11), we have that the angle $\theta$ between the Euclidean line ${\mathrm{\ell }}_{u,v}$ through $u$ and $v$ and the $x$-axis lies in $[0,\pi /4]$ and $|W_{\text{row}}|\ge 2^{100T}$.

For each $x\in {[0,B]}_{\mathbb{Z}}$, let $w_x=(a_x,b_x)$ denote the unique node on $D_{u,v}$ such that $|a_x-\alpha |=x$, and define the function $f:[0,B]\to \mathbb{Z}$ such that $f(x)=p(D_{u,v}[u,w_x])$.

By construction, $f(0)=0$, and by Lemma 11, $f(B)=p\left(D_{u,v}[u,v]\right)=p\left(Q[u,v]\right)=0.$

Next, consider two nodes $w_x=(a_x,b_x)$ and $w_{x+1}=(a_{x+1},b_{x+1})$ in $D_{u,v}$. Observe that $|a_{x+1}-a_x|=1$ and $\mathrm{dist}(w_x,w_{x+1})\le 2$ (which follows from the construction of $D_{u,v}$ which closely follows ${\mathrm{\ell }}_{u,v}$ and the fact that $\theta \in [0,\pi /4]$). Therefore, the value of $f$ on the two nodes differs by at most $2$. More specifically, $|f(x+1)-f(x)|\le 2$ for all $x\in {[0,B-1]}_{\mathbb{Z}}$.

Now fix and set $\mathrm{\ell }≔i$. Since $B\ge 2^{100T}$, it follows that . Define $g(x)≔f(x+\mathrm{\ell })-f(x)$ for $x\in {[0,B-\mathrm{\ell }]}_{\mathbb{Z}}$. Applying the discrete mean value theorem (Lemma 13) with $k=2$ yields an index $x^{\star }\in {[0,B-\mathrm{\ell }]}_{\mathbb{Z}}$ such that $|g(x^{\star })|\le 2$.

Finally, let $u_1≔w_{x^{\star }}=(a_{x^{\star }},b_{x^{\star }})$ and $v_1≔w_{x^{\star }+\mathrm{\ell }}=(a_{x^{\star }+\mathrm{\ell }},b_{x^{\star }+\mathrm{\ell }})$. Then $|a_{x^{\star }+\mathrm{\ell }}-a_{x^{\star }}|=\mathrm{\ell }=i$, and $p\left(D_{u,v}[u_1,v_1]\right)=f(x^{\star }+\mathrm{\ell })-f(x^{\star })=g(x^{\star })$, which implies $|p(D_{u,v}[u_1,v_1])|\le 2$. $◀$

Finally, we describe the adversarial strategy that concludes the proof.

By construction, the diagonal path $D_{u,v}$ can be enclosed in a $(4,\theta )$-parallelogram. The adversary reveals a path $R$ following the strategy in Lemma 8 with $p(R)=10T$ and the path being enclosed in a $(10T+1,\theta )$-parallelogram of horizontal span $2^{10T}\cdot O(T)$ such that the vertical distance between the two parallelograms is $2T+2$ (The exact positioning of the revealed path will be fixed soon). Revealing such a path and forcing the quasilinear boosting on the path is possible as $T=o(\log n)$ and such a path is at a distance at least $2T+2$ from the diagonal-path $D_{u,v}$ as well as the L-path $W$, hence ensuring that the relative positions of the revealed paths remain indistinguishable to the algorithm. This proves Item 1.

Since $R$ is contained in a parallelogram of width $2^{10T}\cdot O(T)$, we obtain $|a_{u_2}-a_{v_2}|\le 2^{10T}\cdot O(T)$. By Lemma 14, there exist nodes $u_1=(a_{u_1},b_{u_1})$ and $v_1=(a_{v_1},b_{v_1})$ with $|a_{u_1}-a_{v_1}|=|a_{u_2}-a_{v_2}|$ such that the diagonal subpath $D_{u,v}[u_1,v_1]$ satisfies $|p\left(D_{u,v}[u_1,v_1]\right)|\le 2$, establishing Item 2. The adversary positions the parallelogram of $D_{u,v}[u_1,v_1]$ keeping $u_1,v_2$ and $v_1,u_2$ aligned on common vertical axes while maintaining the vertical distance of $2T+2$ between the two parallelograms. The dimensions of the parallelograms imply $2T+2\le \mathrm{dist}(D_{u,v}[u_1,v_1],R)\le 12T+7$, as required in Item 3. $◀$

We now have all the ingredients to conclude the deterministic lower bound. The adversary reveals the paths $P_{v_2,u_1}$ and $P_{v_1,u_2}$, which are the shortest paths connecting the endpoints of $D_{u,v}[u_1,v_1]$ and $R$. Each of these length at least $2T+2$. Consider the closed walk

By Lemma 4, the potential of each of the connecting paths is bounded, that is, both $|p(P_{v_1,u_2})|$ and $|p(P_{v_2,u_1})|$ are at most $\frac{12T+7}{3}+c$ for some constant $c$. Hence, if we choose $n$ large enough, then $|p(W)|\ge |10T-2\cdot \frac{12T+7}{3}-2c|>0$, contradicting Lemma 3 and concluding the proof.