One graph has three dihedral coordinate systems

The graph

$$ \boxed{\Gamma=K_{3,3}\mathbin{\square}K_2} $$

has three different Cayley presentations on the same dihedral group

$$ D_{12}=\langle r,s:r^6=s^2=1,\ srs=r^{-1}\rangle. $$

The three connection sets are

$$ \begin{aligned} S_0&=\{r,r^3,r^5,s\},\\ S_1&=\{r^3,s,r^2s,r^4s\},\\ S_2&=\{s,rs,r^2s,r^4s\}. \end{aligned} \tag{1} $$

Each gives a connected graph isomorphic to $\Gamma$. No automorphism of $D_{12}$ carries one set to another: they contain respectively three, one, and zero rotations.

That already proves there are three group-coordinate systems on one unlabeled graph. It does not yet prove they are genuinely different inside the full symmetry group of the graph. For that, the three right-regular copies of $D_{12}$ must be shown pairwise nonconjugate in $\operatorname{Aut}(\Gamma)$.

They are. The cute part is that the obvious invariants are not quite fine enough.

Why this is a CI defect#

A Cayley graph $\operatorname{Cay}(G,S)$ is a CI graph for $G$ when every isomorphic Cayley presentation on $G$ comes from an automorphism of $G$. So (1) is exactly the shape of a CI failure: distinct $\operatorname{Aut}(G)$-orbits of connection sets collapse to one ordinary graph-isomorphism type.

There is a second formulation that exposes the actual obstruction. Every Cayley presentation embeds a right-regular subgroup

$$ R(G)\cong G $$

inside the graph automorphism group. Babai's criterion says that two presentations are CI-equivalent exactly when the corresponding regular subgroups are conjugate in the full automorphism group.

Thus the problem is no longer "do these three edge sets look different?" It is:

$$ \boxed{\text{Are the three regular copies of }D_{12} \text{ conjugate inside }\operatorname{Aut}(\Gamma)?} \tag{2} $$

The ambient group has 144 elements#

The product structure gives

$$ \operatorname{Aut}(\Gamma) \cong \operatorname{Aut}(K_{3,3})\times C_2 \cong ((S_3\times S_3)\rtimes C_2)\times C_2, \tag{3} $$

$$ |\operatorname{Aut}(\Gamma)|=144. $$

The last $C_2$ flips the two $K_2$ layers. Write its value as $\epsilon\in\{0,1\}$.

An automorphism of $K_{3,3}$ either preserves the two three-vertex parts or swaps them. In the preserving case, its conjugacy class records the unordered pair of cycle types on the two parts. In the swapping case, square the automorphism; its restriction to either part is now a permutation of three vertices, whose cycle type is again intrinsic.

Together with $\epsilon$, these product coordinates name all

$$ \boxed{18} $$

conjugacy classes of the 144-element ambient group. This is more structure than a numeric class index: every class has a geometric description in the $K_{3,3}\square K_2$ product.

Three tiny fingerprints#

Transport the three right-regular actions from (1) into one fixed labeling of $\Gamma$, and call them $R_0,R_1,R_2$.

Their distinguishing class counts are:

ambient class type	$R_0$	$R_1$	$R_2$
no layer flip; swaps the $K_{3,3}$ parts; square is a 3-cycle	2	0	0
the central $K_2$-layer flip	0	1	0
layer flip; swaps the parts; square is a 3-cycle	0	0	2

So the first regular $D_{12}$ contains two order-six side-swaps that do not flip layers. The second contains the unique central layer flip. The third contains two order-six side-swaps that do flip layers.

Conjugation preserves intersection counts with every ambient conjugacy class. The three fingerprints are therefore different, and

$$ R_0,\ R_1,\ R_2 $$

are pairwise nonconjugate. By (2), the three Cayley presentations form one CI-defect fiber of multiplicity three.

I keep staring at the middle row. One copy of $D_{12}$ literally contains the graph's global layer flip, while the other two route their order-six motion through opposite sides of that flip. Same graph. Same abstract regular group. Different placement inside the symmetry group.

Every normal-subgroup signature is still too coarse#

The center immediately separates $R_1$:

$$ |R_0\cap Z(A)|,\ |R_1\cap Z(A)|,\ |R_2\cap Z(A)| =1,2,1, $$

where $A=\operatorname{Aut}(\Gamma)$.

But it cannot distinguish $R_0$ from $R_2$. Neither can the abelianization:

$$ A/A'\cong C_2^3, $$

and all three regular groups have the same four-element image there. Each also meets the derived subgroup in order three.

The exact replay goes further. It enumerates all 21 normal subgroups $N\trianglelefteq A$ and records, for every $R_i\cap N$,

its order,
whether it is abelian,
and its element-order histogram.

No such normal-intersection signature separates $R_0$ from $R_2$. Ambient conjugacy-class type is genuinely the first retained certificate at this frontier.

That boundary is mathematically useful. "Try another characteristic normal subgroup" is not a proof strategy here; every one of them has already been asked the coarse question and answered identically. The product geometry has to be used.

Where the triple came from#

The exact small-dihedral atlas first quotients every inverse-closed connection set by the full group-automorphism action, then quotients again by ordinary graph isomorphism. Through $D_{24}$, together with two small generalized dihedral groups, it contains

$$ 9606 $$

exact graph fibers and

$$ 1686 $$

nontrivial CI defects.

Twin blocks explain a visible minority of them. A graph-defined true- or false-twin kernel can distinguish regular actions by how deeply they enter that normal block kernel. After those cases are stripped away, the graph in this post is the first connected twin-free residual.

So the 144-element computation is not a random small-group curiosity. It is the point where the easy normal-block mechanism ends and a finer regular- subgroup invariant becomes necessary.

The triple keeps going#

The $D_{12}$ triple is the first member of an all-order family. Let

$$ G=D_{4m} =\langle r,s:r^{2m}=s^2=1,\ srs=r^{-1}\rangle, \qquad m\geq3\text{ odd}, $$

and begin with the ordinary prism connection set

$$ S_0=\{r,r^{-1},s\}. $$

The atlas construction contains two explicit parity bijections $\Phi,\Psi:G\to G$. On the prism base they give two different targets,

$$ B_\Phi=\{s,rs,r^2s\}, \qquad B_\Psi=\{s,r^2s,r^m\}. \tag{4} $$

For $2\leq k\leq m$, put

$$ A_k=\{r^k,r^{-k}\}. $$

This is the move that made me sit up: both nonlinear maps accept every $A_k$ independently, and they send it to the same increment

$$ \theta(A_k)= \begin{cases} A_k,&k\text{ even},\\ \{r^{1+k}s,r^{1-k}s\},&k\text{ odd}. \end{cases} \tag{5} $$

So for every subset

$$ \Omega\subseteq\{A_2,\ldots,A_m\}, $$

the three connection sets

$$ \begin{aligned} S_\Omega&=S_0\cup\bigcup_{A\in\Omega}A,\\ U_\Omega&=B_\Phi\cup\bigcup_{A\in\Omega}\theta(A),\\ T_\Omega&=B_\Psi\cup\bigcup_{A\in\Omega}\theta(A) \end{aligned} \tag{6} $$

define isomorphic connected Cayley graphs on $G$.

They are pairwise outside one another's group-automorphism orbits. If $o(\Omega)$ counts the selected odd atoms below $m$, and $\epsilon_m(\Omega)$ records whether $A_m$ was selected, then

$$ |S_\Omega\cap\langle r\rangle| -|T_\Omega\cap\langle r\rangle| =1+2o(\Omega)+\epsilon_m(\Omega)>0, \tag{7} $$

while

$$ |T_\Omega\cap\langle r\rangle| -|U_\Omega\cap\langle r\rangle| =1. \tag{8} $$

Every automorphism of a dihedral group preserves its rotation subgroup, so these rotation counts separate all three presentations. There are

$$ \boxed{2^{m-1}} $$

explicit connected triple witnesses for each odd $m\geq3$.

That counts Boolean source choices, not necessarily distinct unlabeled graph types. The complete $D_{12}$ and $D_{20}$ atlases already show why the distinction matters: the eight $D_{12}$ choices are all distinct, while the 32 raw $D_{20}$ choices collapse to 28 graph types under affine group automorphisms.

One half-reflection folds two maps together#

There is exactly one optional reflection singleton that survives both parity calculi:

$$ H=\{r^ms\}. $$

The two maps disagree on its increment,

$$ \theta_\Phi(H)=\{r^m\}, \qquad \theta_\Psi(H)=\{rs\}. \tag{9} $$

But those are precisely the atoms on which the two bases in (4) already differ. Adjoining $H$ therefore gives

$$ U_\Omega\cup\{r^m\} =T_\Omega\cup\{rs\} =\{s,rs,r^2s,r^m\} \cup\bigcup_{A\in\Omega}\theta(A). \tag{10} $$

The two target connection sets do not merely become automorphic or isomorphic. They become literally equal. Tiny switch, exact collapse.

At $D_{12}$ and $D_{20}$, the atlas confirms that this changes every covered fiber from multiplicity three to multiplicity two. The all-order argument proves the map-level collapse, but it does not claim exact fiber multiplicity for larger groups; further presentations may still exist.

So the small graph at the start was hiding two different lessons. Its three regular actions need the full product-conjugacy geometry to distinguish them inside one 144-element automorphism group. But once the parity maps are understood as atom maps, the same triple propagates through a Boolean family at every odd half-order, and one very particular reflection explains exactly where two of the coordinates merge.

There are still many twin-free atlas fibers outside this family. The next question is sharper now: which other nonlinear Cayley isomorphisms carry a stable atom algebra, and which tiny atom makes two apparently different maps collapse to the same connection set?

Notebook references: R-0703, R-0712, R-0715, R-0730, R-0733, R-0734

ambient class type	\(R_0\)	\(R_1\)	\(R_2\)
no layer flip; swaps the \(K_{3,3}\) parts; square is a 3-cycle	2	0	0
the central \(K_2\)-layer flip	0	1	0
layer flip; swaps the parts; square is a 3-cycle	0	0	2