Message Boards

GROUPS:

Daksh Aggarwal

[WWS21] Multiway Systems as Cayley Graphs

Daksh Aggarwal, Grinnell College

Posted 1 year ago

3147 Views

3 Replies

9 Total Likes

Follow this post

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 We can then get rid of the garbage pairs (for example, because they aren’t part of the largest connected component) to obtain the subgraph, which again needs some vertices to be stuck to extract the Cayley graph of Klein 4. The question that arises is: given a subgraph H that potentially represents a Cayley graph, how do we decide which vertices to stick, and even before that, how many to stick? One approach is to define equivalence relations along orbits of the action of Aut (H) , but this doesn’t work because vertex transitivity is not necessarily preserved under “vertex sticking.” So, I have ultimately resorted to a brute-force approach: running through all possible equivalence relations. A little more precisely: given a subset of vertices U⊂V(H) , “project” V(H) onto U by identifying w∈V(H)\U with a vertex v ∈ U such that d(w,v) is minimized in H . From these various possible projections, I choose the nonisomorphic ones which satisfy vertex transitivity; this list of potential graphs may then be tested using CayleyQ . Examples with the function PotentialCayley are below. Cyclic group of order 3 In[]:= g3=ResourceFunction["MultiwayGroup"][<\|"Generators"{"a"},"Relations"{},"Identity""e","Inverses"{"aa"}\|>,4,"StatesGraph"]; In[]:= PotentialCayley[g3,"All"] 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 In[]:= k4=ResourceFunction["MultiwayGroup"][<\|"Generators"{"a","b"},"Relations"{"ab""ba"},"Identity""e","Inverses"{"a","b"}\|>,4,"StatesGraph"]; In[]:= PotentialCayley[k4] 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 In[]:= g5=ResourceFunction["MultiwayGroup"][<\|"Generators"{"a"},"Relations"{},"Identity""e","Inverses"{"aaaa"}\|>,4,"StatesGraph"]; PotentialCayley[g5,"All"] Out[]= For Z/5Z , 6 potential Cayley graphs are identified, fourth of which is the true Cayley graph of the group (it is in natural form). Dihedral group D 3 In[]:= d3=ResourceFunction["MultiwayGroup"][<\|"Generators"{"r","s"},"Relations"{"rs""srr"},"Identity""e","Inverses"{"rr","s"}\|>,3,"StatesGraph"]; CayleyGraph[DihedralGroup[3]] Out[]= PotentialCayley[d3,6] Out[]= Mixed results are obtained for D 3 . The extracted subgraph from the multiway is too large to cycle through all possible projections, so a specification of the number of vertices is required. On the other hand, the second graph it identifies is structurally indeed the correct Cayley graph, though the generators are not canonical and the identity vertex is not included. 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: ◼ Needless to say, a fully working CayleyQ is desirable; one hurdle here is to build functionality to enumerate all subgroups of a given group (specified as a subgroup of a symmetric group) in WL. ◼ 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. ◼ Test PotentialCayley with groups of larger orders. Further, test with random string substitution systems; to do this, however, all functionality will have to be made more efficient. ◼ 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.

POSTED BY: Daksh Aggarwal

3 Replies

Sort By:

Sam Willis

Posted 1 year ago

This is really cool! Didn't realise we were doing projects with themes that crossed over!

POSTED BY: Sam Willis

Moderation Team

Moderation Team, WOLFRAM

Posted 1 year ago

-- you have earned *Featured Contributor Badge* Your exceptional post has been selected for our editorial column *Staff Picks* http://wolfr.am/StaffPicks and Your Profile is now distinguished by a *Featured Contributor Badge* and is displayed on the Featured Contributor Board. Thank you!