Multiway systems as Cayley graphs​
Daksh Aggarwal
Grinnell College, IA, USA
Determine if a given multiway system is the simulation of a group presentation.

Motivation

One of the important questions associated with the Wolfram models is understanding the limiting structure of multiway systems. Wolfram [7, pp. 233] suggests that one way to make progress on this problem is by using Cayley graphs of algebraic structures as models of growth for neighborhoods in a multiway system. The success of such an approach would, for example, enable the application of results from geometric group theory, which has come to serve as a productive bridge for flow of ideas from topology and geometry to groups. Specifically, a number of results [e.g. see 5 & 6] could shed light on growth rates of multiway system, thus aiding in the classification of multiway limiting structure. Moreover, a possible correspondence between Cayley graphs and multiway systems is interesting even when we are not concerned about the continuum limit. Such a correspondence could, for instance, potentially assist in the discovery of equivalent rewriting rules for a multiway system. This project begins to lay the groundwork for this correspondence, by attempting to identify if a given multiway system can be viewed as the multiway evolution of the presentation of a finite group.

Cayley Graphs

Groups are sets equipped with a binary operation that has associativity, an identity, and inverses for all elements. There exist many points of view in the study of groups. For instance, groups arise naturally in basic familiar structures like (
Z,+
), (
Q\{0},
), and (
GL
n
(R),
). Groups also arise as invariants of topological spaces. The point of view, however, most interesting to us is perhaps best captured by Cayley’s theorem: every finite group
G
is isomorphic to a subgroup of
S
G
the symmetric group on
G
elements. So we are interested in a group as a set of automorphisms. The crux of Cayley’s theorem lies in being able to think of
G
as acting on itself and a useful way of visualizing
G
as a
G
-set is a Cayley graph. The Cayley graph
C(G,G)
has vertices corresponding to the elements of
G
and we draw a directed edge
(u,v)
if
-1
u
v∈G
. Of course,
C(G,G)
is not really interesting because it is isomorphic to
K
G
. We can instead consider
C(G,S)
for a subset
S⊂G
, where we draw
(u,v)∈
2
G
if
-1
u
v∈S
. The most common choice of
S
is a set of generators of
G
. For instance, for finite cyclic group
Z/nZ
we could take
S
to be one of its generators; for the dihedral group
D
n
we take
S{r,s}
where
n
r

2
s
e
and
rss
-1
r
.
​​
CayleyGraph/@{CyclicGroup[10],AbelianGroup[{2,2,2}],DihedralGroup[6]}
Out[]=
Figure 1: Cayley graphs of
Z/10Z
,
3
(Z/2Z)
, and
D
6
We can also consider Cayley graphs for infinite groups, such as the free group on
n
generators, and for other algebraic structures such as monoids and semigroups. This project, however, focuses on finite groups.
Figure 2: An evolving Cayley graph of the free group on two generators [Source]

Group Presentations as String Substitution Systems

Consider the cyclic group
Z/3Z
; it has a presentation
<a|
3
a
1>
. We can simulate this presentation as a string substitution system:
​​ResourceFunction["MultiwaySystem"][{"a""aa","a""ae","a""aaa","e""ea","e""ee","e""eaa","aa""aaa","aa""aae","aa""aaaa","ae""a","ea""a","ee""e","aae""aa","eaa""aa","aaa""e"},{"e","a","aa"},2,"EvolutionGraph"]
Out[]=
Figure 3: Evolution of
Z/3Z
as a multiway system
​
​Note that there are two types of rules: those which represent (1) multiplication with a generator (e.g. “a”

“aa”, “e”

“ea”) and (2) the relations of group (e.g. “a”

“ae”, “aaa”

“e”). The application of different types of rules is highlighted in different colors by
MultiwayGroup
.
ResourceFunction["MultiwayGroup"][<|"Generators"{"a"},"Relations"{},"Identity""e","Inverses"{"aaa"}|>,2,"StatesGraph"]
Out[]=
Figure 4: States graph of
Z/3Z
as a multiway system.
​​
≡
generator,
≡
identity,
≡
inverse,
≡
other relations (none here)
The problem I have been studying is, for example, given the states graph above, how can we determine that it is actually the multiway simulation of a group presentation? Besides the messy nature of these graphs, one of the reasons this problem is tricky is that, in general, the honest-to-goodness Cayley graph of
G
might not even be a subgraph of the multiway simulation of
G
.
For instance, in the multiway system evolution of
Z/4Z
the smallest connected component induced by {“e”, “a”, “aa”, “aaa”} is:
Figure 5: Equivalent vertices need to be stuck together to obtain the true Cayley graph
​​
So to recover the actual Cayley graph we have to induce an equivalence relation on the vertices that are connected via edges not representing applications of a generator.

When is a Graph Cayley?

Before trying to answer the question asked above, it is insightful to consider the easier problem of when a given directed graph is a Cayley graph of some group. There hasn’t been any recent progress on this and the best characterization is Sabidussi’s [4, 1]: a directed graph
G
is Cayley if and only if its automorphism group Aut
(G)
has a subgroup that acts freely and transitively on
G
. This characterization is in some sense trivial: for any two elements
u,v
in a group
G
, we know
g
-1
u
v∈G
is unique and since
g
is an automorphism of
C(G,S)
via left multiplication:
u↦gu
, the result follows. I have attempted to implement this in
CayleyQ
that returns the generators of a subgroup, if it finds one, of Aut
(G)
that acts freely and transitively on
G
and otherwise
False
. This function is incomplete since the Wolfram language presently doesn’t have a built-in capability to generate all subgroups of arbitrary finite group; so the result
False
might mean that my function missed a subgroup. On the other hand, the function seems to work for common groups.
CayleyQ[CayleyGraph[CyclicGroup[100]]]
Out[]=
PermutationGroup[{Cycles[{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100}}]}]
CayleyQ[CayleyGraph[DihedralGroup[10]]]
Out[]=
PermutationGroup[{Cycles[{{1,2},{3,4},{5,6},{7,8},{9,10},{11,12},{13,14},{15,16},{17,18},{19,20}}],Cycles[{{1,3},{2,19},{4,5},{6,7},{8,9},{10,11},{12,13},{14,15},{16,17},{18,20}}]}]
CayleyQ[CayleyGraph[AbelianGroup[{2,4}]]]
Out[]=
PermutationGroup[{Cycles[{{1,2,3,4},{5,6,7,8}}],Cycles[{{1,5},{2,6},{3,7},{4,8}}]}]
The path graph is not Cayley since it is not even regular.
CayleyQ[Graph[{12,23,34,45}]]
Out[]=
False
Note the very definition of
C(G,S)
and the fact that
G
acts on it via left multiplication imply that
C(G,S)
is vertex transitive. It is actually quite difficult to find vertex transitive graphs that are not Cayley [e.g. see 0]. The smallest counterexample is Petersen’s graph.
PetersenGraph[5,2]
Out[]=
CayleyQ[PetersenGraph[5,2]]
Out[]=
False

Attempting to Uncover Cayley Graphs

The first question is: given the multiway system of
Z/3Z
in Figure 4, how do we extract the much more pleasant subgraph in Figure 5? Remember, of course, that we don’t have access to the vertex labels; we have to purely work with the graph-theoretic structure. An implicit assumption is that the multiway structure has been allowed to evolve long enough to contain the entire Cayley graph (up to an equivalence relation of vertices as in Figure 4) of the group; pieces of Cayley graphs cannot be identified. There are a few simple properties along with some heuristics I have used to extract the subgraph. Perhaps one of the simplest one is this:
C(G,S)
has to be strongly connected. But trying to directly extract strongly connected components from a large states graph is going to be quite slow. So I first clean up the states graph using considerations of degree and then vertex transitivity. To give an idea, here is a (questionable) heuristic I have used: sometimes there are pairs of vertices
{u,v}
with both edges
uv
and
vu
; this can be interpreted as
uv
in
G
.
Another seeming interpretation might be that
s
-1
u
v∈S
has order 2 in
G
but in this case the shortest path would be
vusussueu
. So since
uv
, we do not loose any part of the Cayley graph by deleting one of
u
or
v
(except in some special situations). Such kinds of deletions create further garbage vertices that are cleaned up, thus gradually reducing to a size potentially amenable to finding strongly connected components. For example, running this extraction procedure on the multiway states graph of Klein 4 =
<a,b
2
a

2
b
e,abba>
, we obtain the following subgraph.
Figure 6: Subgraph extracted from the states graph of Klein four-group

​
Cyclic group of order 3

The last graph represents the true Cayley graph. The first two are also Cayley graphs, and so this example highlights that this method might not produce a unique Cayley graph.

Klein 4

​
We recover the Cayley graph of Klein 4, albeit vertex labels are not in simplest form and the generator “ab” rather than “b” is being used.

Cyclic group of order 5

Future directions

This project has demonstrated that the inverse problem of checking if a multiway system corresponds to a Cayley graph can potentially be fully solved, with the following specific points requiring further work:
◼
  • Better characterizations of when the projection of a given graph will yield at least a vertex transitive graph. Here, my brute force approach could also be significantly improved using a dynamic programming approach.
    • ◼
  • Extend functionality to other algebraic structures such as monoids and semigroups.

    • Keywords

    ◼
  • Multiway systems
    • ◼
  • Cayley graphs
    • ◼
  • Automorphisms
    • ◼
  • Finite groups

    • Acknowledgment

    Mentor: Manojna Namuduri
    I would like to thank Mano for many useful discussions and insightful suggestions. Thanks to Jonathan Gorard, Xerxes Arsiwalla, and Stephen Wolfram for suggesting this project and guiding me, and to all the staff who made this Winter School so enjoyable and accessible.

    References

    ◼
  • [0] B.D. Mckay and G.F. Royle,“The transitive graphs with at most 26 vertices,” Ars Combin, vol.30, pp.3–7, 1990.
    • ◼
  • [1] D. Caucal, "Structural characterization of Cayley graphs," arXiv:1609.08272 [cs, math], Sep. 2016, Accessed: Jan. 05, 2021. [Online]. Available: http://arxiv.org/abs/1609.08272.
    • ◼
  • [2] C. Adiga and H. Ariamanesh, "Some Properties of Cayley Graphs on Symmetric Groups Sn," p. 7.
    • ◼
  • [3] D. Caucal, "On Cayley graphs of algebraic structures," arXiv:1803.08518 [cs, math], Mar. 2018, Accessed: Jan. 05, 2021. [Online]. Available: http://arxiv.org/abs/1803.08518.
    • ◼
  • [4] G. Sabidussi, "On a Class of Fixed-Point-Free Graphs," Proceedings of the American Mathematical Society, vol. 9, no. 5, pp. 800–804, 1958, doi: 10.2307/2033090.
    • ◼
  • [5] R. I. Grigorchuk, "Degrees Of Growth Of Finitely Generated Groups, and the Theory Of Invariant Means," Math. USSR Izv., vol. 25, no. 2, p. 259, Apr. 1985, doi:10.1070/IM1985v025n02ABEH001281.
    • ◼
  • [6] J. Milnor,“A note on curvature and fundamental group,” J.Differential Geom., vol.2, no.1, pp.1–7, 1968, doi:10.4310/jdg/1214501132.
    • ◼
  • [7] S. Wolfram, “A Class of Models with the Potential to Represent Fundamental Physics,” Complex Systems, vol. 29, no. 2, pp. 107–536, Jun. 2020, doi: 10.25088/ComplexSystems.29.2.107.