The super graph of the Stomachion tilings
There are
17152 (=64 x 268) different Stomachion tilings.
In addition to the local and global moves, we can take
a geometric step by interchanging two
congruent pieces.
The super graph with 17152 vertices can be explained
in two ways --- top down or bottom up.
Bottom up
Step 0: Take one copy of the STOMACH graph, called it G = G0.
Step 1:Take another copy of the STOMACH graph.
Join two copies by a
perfect matching
(corresponding to the swapping of the first pair of congruent pieces).
Call the resulting graph
G1.
Step 2: Take two copies of
G1
to form
G2. Join them by a perfect matching
(corresponding to the swapping of the second pair of congruent pieces).
Step 3:Take two copies of
G2
to form
G3.
Join them by a perfect matching
(corresponding to the swapping of the second pair of congruent pieces).
Step 4:
Take 8 copies of
G3 and join every pair of copies of
G3 by a perfect matching
(corresponding to the moves by the dihedral group).
We are done. The resulting graph is the super graph.
Top down
The 17152 (=64 x 268) vertices are partitioned into 64 blocks each with
268 vertices.
Each block is a copy of G, the STOMACH graph.
The super graph is the cartesian product G
×
K2
×
K2
×
K2
×
K8.
Terminology: For two graphs G =(V,E) and G' =(V',E'), the cartesian product G x G' is the graph with vertex set
(u,u'), u in V and u' in V'. (u,u') is adjacent to (v,v') if either
{u=v and (u',v') in E'}
or {u'=v' and (u,v) in E}.
Kn
is the complete graph on n vertices.