Cayley graphs on binary strings with $k$ zeros and $n-k$ ones, generated by 3-consecutive cycles.
This page gives a brief summary of recent notes on the holography analysis of $G_3(k,n)$ in the context of the CayleyPy project (see A. V. Chervov et al.)
This interactive application can be used to generate $G_3(k,n)$ graphs, visualize them in various forms, illustrate holography, compute statistics, explore related examples, etc. Please use the Help section in the application for more details.
Holography rule. Let $A = 0^k1^{n-k}$, and consider a $k \times (n-k)$ rectangle. For a binary string $X$, draw a path using the rule: $0 =$ move right and $1 =$ move up. Let $U$ be the area under this path.
In most cases, $$d(A,X) = \left\lceil \frac{U}{2} \right\rceil.$$ In a few exceptional cases, $$d(A,X) = \left\lceil \frac{U}{2} \right\rceil + 1.$$ We refer to such cases as mismatches.
Mismatches first appear when $k=3$ and $n=6$.
Assume $n \ge 3$ and $1 \le k \le n-1$. Let $$A = 0^k1^{n-k}.$$
For any vertex $B$, let its zero positions be $$1 \le z_1 < z_2 < \cdots < z_k \le n,$$ and define $$ d_i := z_i - i, \qquad I(B) := \sum_{i=1}^k d_i, \qquad \Delta(B) := \left| \sum_{i=1}^k (-1)^{i+1}(d_i \bmod 2) \right|. $$
Then the exact distance from the canonical vertex $A$ to $B$ is $$ \boxed{ d_{G_3(k,n)}(A,B) = \frac{I(B)+\Delta(B)}{2} }. $$
For arbitrary vertices $X$ and $Y$, with ordered zero positions $$ X:\ 1 \le x_1 < \cdots < x_k \le n, \qquad Y:\ 1 \le y_1 < \cdots < y_k \le n, $$ the following sharp general bounds hold: $$ \boxed{ \left\lceil \frac{1}{2}\sum_{i=1}^k |x_i-y_i| \right\rceil \le d_{G_3(k,n)}(X,Y) \le \sum_{i=1}^k \left\lceil \frac{|x_i-y_i|}{2} \right\rceil }. $$
The diameter is $$ \boxed{ D(G_3(k,n)) = \left\lceil \frac{k(n-k)}{2} \right\rceil }. $$
There are no mismatches when $k=1$, for all values of $n$.
There are no mismatches when $k=2$, for all values of $n$.
There are no mismatches when $k=3$ and $n < 6$. Mismatches start at $n=6$.
This mismatch statistics table gives statistics for $G_3(3,n)$ for $n$ up to 100.
Please see this application for the dynamics of Consecutive 3-Cycle Moves.
