Limited rook moves

Question

I have an algebra problem, that could be solved if I could answer the following combinatorial problem.

Let $S$ and $T$ be two nonempty sets. We think of $S\times T$ as the index set for the squares of a rectangular chessboard.

Let $\emptyset\neq P\subseteq S\times T$. We think of $P$ as indices of certain special squares of the chessboard. We can call them the on-squares, while $S\times T-P$ are the indices of the off-squares.

We think of the on-squares as places where rooks can land. A rook can pass over off-squares, but can only move from one on-square to another on-square. (In other words, a rook can move from $(s,t_1)$ to $(s,t_2)$; or from $(s_1,t)$ to $(s_2,t)$, assuming those pairs are in $P$.)

We make the following assumptions about $P$:

(1) Any two squares indexed by $P$ are connected by a finite sequence of rook moves.

(2) For every $s\in S$, there is some $t\in T$ such that $(s,t)\in P$; and similarly for every $t\in T$ there is some $s\in S$ such that $(s,t)\in P$. (In other words, no column or row of our chessboard consists only of off-squares.)

For example, consider the $3\times 3$ board below, where we have placed $\bullet$'s on the on-squares and $\circ$'s on the off-squares. $$ \begin{array}{|c|c|c|} \hline \bullet & \circ & \circ \\ \hline \bullet & \circ & \bullet \\\hline \circ & \bullet & \bullet\\\hline \end{array} $$ We can get from any on-square to any other on-square by a sequence of no more than 4 rook moves.

We make one further, invariance assumption.

(3) If $(i,j),(k,l)\in P$, then the map $i\mapsto k$ extends to a permutation $\sigma$ of $S$, and the map $j\mapsto l$ extends to a permutation $\tau$ of $T$, such that $\sigma\times \tau$ induces an permutation of $P$. In other words, up to renaming the rows and columns, any on-square looks exactly like any other on-square.

---

That's the set-up. To motivate my question, consider the case when on-squares are connected by a sequence of at most two rook moves. This holds, for instance, when all squares are on-squares. However, consider the case when there is an off-square. Then there is a partial diagram of the form $$ \begin{array}{|c|c|} \hline \bullet & \\ \hline \circ & \bullet \\ \hline \end{array} $$ The upper right corner must then be an on-square, else we cannot connect the two on-squares in two moves. So, the diagram must fill in as $$ \begin{array}{|c|c|} \hline \bullet & \bullet \\ \hline \circ & \bullet \\ \hline \end{array} $$ The lower right square is connected by a column then row move to another on-square, but it isn't connected to that on-square by a row move followed by a column move. Thus, by condition (3), the upper left square also has to have this property. So the diagram expands as $$ \begin{array}{|c|c|c|} \hline \bullet & \bullet & \\ \hline \circ & \bullet & \bullet \\ \hline &\circ & \bullet \\ \hline \end{array} $$ The upper right square is then forced to be on, and the lower left square is forced to be off.

Continuing this process, one obtains an infinite chessboard whose on-squares are all in the upper right part, and the off squares are in the lower left half. It still isn't invariant unless one makes some additional modifications, but it is possible to form such a board.

Here is my question:

If we instead assume that all on-squares are connected by 3 moves or less, is it possible for some of the on-squares to only be connected by row, then column, then row moves, but not column, then row, then column moves (including trivial moves)?

Answer 1

Yes, this is possible. The sets $$\mathbb A := \mathbb Q \setminus \{i 2^j \mid i,j \in \mathbb Z\} $$ and $$\mathbb B :=\{B_{i,j}:=(i2^j,(i+1)2^j) \mid i,j \in \mathbb Z\}$$ are countable - the important bit here is that for fixed $j$, the $B_{i,j}$ are a disjoint cover of $\mathbb A$, and that any $B_{i,j+1}$ is a union of two of the $B_{i,j}$.

Instead of a $(\mathbb Z \times \mathbb Z)$-board consider an $(\mathbb A \times \mathbb B)$-board with on-squares $(a,b)$ for $a \in b$.

Any two on-squares are connected by a sequence of three moves since any two intervals in $\mathbb B$ have a common upper bound (w.r.t. union) in $\mathbb B$, in particular (1) holds. Property (2) holds since any element of $\mathbb A$ is contained in infinitely many intervals in $\mathbb B$. To see that (3) holds is a bit trickier. Note that the following maps $\mathbb Q \to \mathbb Q$ setwise preserve $\mathbb A$ and $\mathbb B$ for $i,j\in \mathbb Z$, $i$ even: $$ \phi_j \colon q \mapsto 2^j q \qquad \text{and} \qquad \psi_{i,j} \colon q \mapsto \begin{cases} q+2^j & i2^j < q \leq (i+1)2^j \\ q-2^j & (i+1)2^j < q \leq (i+2)2^j\\ q&\text{otherwise} \end{cases} $$ A map between elements $(a_1,b_1)$ and $(a_2,b_2)$ can be constructed as a limit of the above maps: First note that there is $j_0\in \mathbb Z$ such that $\phi_{j_0} (b_1)$ and $b_2$ have the same length. Next note that there is some $J \in \mathbb Z$ such that $\phi_{j_0} (a_1)$ and $a_2$ lie in the same $B_{i,J}$. If they don't lie in the same $B_{i,J-1}$ then $\psi_{i,J-1} (\phi_{j_0} (a_1))$ and $a_2$ do. Proceed inductively for j=J-2,J-3,etc. always applying an appropriate $\psi_{i,j}$ when necessary to ensure that the image of $a_1$ lies in the same $B_{i,j}$ as $a_2$.

Note that every $q \neq a_1$ is only affected by finitely many of the $\psi_{i,j}$ (depending on the distance between $a_1$ and $q$) and that the images of $a_1$ converge to $a_2$. In particular the limit map $f \colon \mathbb Q \to \mathbb Q$ is well defined with $f(a_1)= a_2$. Moreover, $f$ preserves $\mathbb B$ setwise since every $B_{i,j}$ is setwise fixed by all but finitely many $\psi_{i,j}$, and clearly $f(b_1) = b_2$.

Finally, the only paths of length 3 from $(a,B_{0,0})$ to $(a+1,B_{1,0})$ are of the form $$(a,B_{0,0}) , (a,B_{0,j}) , (a+1,B_{0,j}) (a+1,B_{1,0})$$ for some $j > 0$ (note that at some point we have to change the $a$ to an $a+1$, and we can only do this if we change the $\mathbb B$-coordinate before and after it).