# 4.17 Manifolds and Model Spaces

We saw above a rule which generates a sequence of hypergraphs like this:

ResourceFunction["WolframModelPlot"][ ResourceFunction[ "WolframModel"][{{1, 2, 2}, {3, 1, 4}} -> {{2, 5, 2}, {2, 3, 5}, {4, 5, 5}}, {{0, 0, 0}, {0, 0, 0}}, #, "FinalState"], ImageSize -> Tiny] & /@ {100, 200, 400, 800}

We can think of this after an infinite number of steps as giving an infinitely fine meshor in effect a structure which limits to a two-dimensional manifold. In standard mathematics, the defining feature of a manifold is that it is locally like Euclidean space (in some number of dimensions d) . By using Euclidean space as a model many things can be defined and computed about manifolds (e.g. ).

Some of our models here yield emergent geometry whose limit is an ordinary manifold. But the question arises of what mathematical structures might be appropriate for describing the limiting behavior of other cases. Is there perhaps some other kind of model space whose properties can be transferred?

It is tempting to try to start from Euclidean space (or n), and define some subset such as a Cantor set. But it seems more likely to be fruitful to start from convenient discrete structures, and see how their limits might correspond to what we have. One important feature of Euclidean space is its uniformity: every point is in a sense like every other, even if different points can be labeled by different coordinates.

So this suggests that by analogy we could consider graphs (and hypergraphs) whose vertices all have the same graph neighborhood (vertex transitive graphs). Several obvious infinite examples are the limits of:

HexagonalGridGraphHex[wide_] := Module[{cells, edges, vertices, vcount, simpleedges}, cells = Table[If[ Abs[a + b] <= wide - 1, {{-Sqrt, -1}, {-Sqrt, 1}, {0, 2}, {Sqrt, 1}, {Sqrt, -1}, {0, -2}} + Table[{2 Sqrt a + Sqrt b, 3 b}, {6}], Sequence @@ {}], {a, -wide + 1, wide - 1}, {b, -wide + 1, wide - 1}]; edges = Union[Sort /@ Flatten[(Partition[#, 2, 1, 1] & /@ Flatten[cells, 1]), 1]]; vertices = Union[Flatten[edges, 1]]; Graph[UndirectedEdge @@@ edges, VertexCoordinates -> Thread[vertices -> vertices]]]; spatialstyles = Sequence[ VertexStyle -> ResourceFunction["WolframPhysicsProjectStyleData"][ "SpatialGraph", "VertexStyle"], EdgeStyle -> ResourceFunction["WolframPhysicsProjectStyleData"][ "SpatialGraph", "EdgeLineStyle"]] ; {GridGraph[{20, 20}, ImageSize -> {Automatic, 100}, spatialstyles], Graph[HexagonalGridGraphHex, ImageSize -> {Automatic, 100}, spatialstyles], GridGraph[{8, 8, 8}, ImageSize -> {Automatic, 100}, spatialstyles], TreePlot[KaryTree, Center, ImageSize -> {Automatic, 100}, spatialstyles], TreePlot[KaryTree[Sum[3^i, {i, 4}], 3], Center, ImageSize -> {Automatic, 100}, spatialstyles]}

Any uniform tessellation or regular tree provides an example. One might think that another example would be graphs formed by uniform application of a vertex substitution rulesuch as “spherical Sierpiński graphs” starting from a tetrahedron, dodecahedron or buckyball graph:

unorderedHyperedgesToGraph[edges_] := Catenate[Replace[edges, vertices_ :> Thread[Unique[] -> vertices], {1}]] nestgraph[g_, t_, opts___] := Graph3D[UndirectedEdge @@@ ((ResourceFunction[ "WolframModel"][{{0, 1}, {2, 1}} -> {{0, 2}}, #, "FinalState"] &)@ ResourceFunction[ "WolframModel"][{{0, 1}, {0, 2}, {0, 3}} -> {{4, 5}, {6, 5}, {4, 7}, {8, 7}, {6, 9}, {8, 9}, {4, 1}, {6, 2}, {8, 3}}, Reverse /@ (List @@@ unorderedHyperedgesToGraph[List @@@ EdgeList[g]]), t, "FinalState"]), opts, VertexStyle -> ResourceFunction["WolframPhysicsProjectStyleData"][ "SpatialGraph3D", "VertexStyle"], EdgeStyle -> ResourceFunction["WolframPhysicsProjectStyleData"][ "SpatialGraph3D", "EdgeLineStyle"]]; {nestgraph[GraphData["TetrahedralGraph"], 4, ImageSize -> 150], nestgraph[GraphData["DodecahedralGraph"], 2, ImageSize -> 150], nestgraph[ResourceFunction["BuckyballGraph"], 2, ImageSize -> 150]}

But (as mentioned in 4.8) in these graphs not every vertex has exactly the same neighborhood, at least if one goes beyond geodesic distance 2. The number of distinct neighborhoods does, however, grow fairly slowly, suggesting that it may be possible to consider such graphs “quasi vertex transitive” (in rough analogy to quasiconformal).

But one important class of graphs that are precisely vertex transitive are Cayley graphs of groupsand indeed the infinite tessellation and tree graphs above are all examples of these. (Note that not all vertex-transitive graphs are Cayley graphs; the Petersen graph is an example . It is also known that there are infinite vertex-transitive graphs that are not Cayley graphs , and are not even “close” to any such graphs .)

In a Cayley graph for a group, each node represents an element of the group, and each edge is labeled with a generator of the group. (Different presentations of the groupwith different choices of generators and relationscan have slightly different Cayley graphs, but their infinite limits can be considered the same.) Each point in the Cayley graph can then be labeled (typically not uniquely) by a word in the group, specified as a product of generators of the group.

One can imagine progressively building up a Cayley graph by looking at longer and longer words. In the case of a free group with two generators A and B, this yields:

ToBars[string_] := Row[If[LowerCaseQ[#], OverBar[ToUpperCase[#]], #] & /@ Characters[string]]; Table[With[{g = ResourceFunction[ "CayleyNestGraph"][{{"A", "B", "a", "b"}, {}}, {""}, n]}, TreePlot[g, Center, VertexLabels -> If[n > 2, None, (# -> ToBars[#] & /@ VertexList[g])], ImageSize -> n 200/3]], {n, 3}]

If one adds the relation AB = BA, defining an Abelian group, the Cayley graph is instead a grid, with “coordinates” given by the numbers of As and Bs (or their inverses):

ToBars[string_] := Row[If[LowerCaseQ[#], OverBar[ToUpperCase[#]], #] & /@ Characters[string]]; Table[With[{g = ResourceFunction[ "CayleyNestGraph"][{{"A", "B", "a", "b"}, {"AB" <-> "BA", "ab" <-> "ba", "Ba" <-> "aB", "Ab" <-> "bA", "Aa" -> "", "aA" -> "", "bB" -> "", "Bb" -> ""}}, {""}, n]}, Graph[g, GraphLayout -> "SpringElectricalEmbedding", VertexLabels -> (# -> ToBars[#] & /@ VertexList[g])]], {n, 3}]

Here are the Cayley graphs for the first few symmetric and alternating (finite) groups:

GraphicsRow[ Table[Labeled[ CayleyGraph[SymmetricGroup[n], ImageSize -> {110, 110}], TraditionalForm[ Text[Subscript["S", n], BaseStyle -> {GrayLevel[.25], FontSize -> .95 Inherited, FontFamily -> "Source Serif Pro"}]]], {n, 2, 5}], ImageSize -> 500]
GraphicsRow[ Table[Labeled[ CayleyGraph[AlternatingGroup[n], ImageSize -> {110, 110}], TraditionalForm[ Text[Subscript["A", n], BaseStyle -> {GrayLevel[.25], FontSize -> .95 Inherited, FontFamily -> "Source Serif Pro"}]]], {n, 3, 6}], ImageSize -> 500]

For a given infinite Cayley graph, one can compute a limiting Vr just as we have for hypergraphs. If one picks a finite number of generators and relations at random, one will usually get a Cayley graph that has a basically tree-like structure, with a Vr that grows exponentially. For nilpotent groups, however, Vr always has polynomial growthan example being the Heisenberg group H3 whose Cayley graph is the limit of :

expandColorRules[n_, defaultcolors_] := Switch[defaultcolors, Automatic, PadRight[{}, n, {Hue[0.599116, 0.480955, 0.709798], Hue[0.202127, 0.82, 0.62], Hue[0.041225144751899624, 0.8, 0.88], Hue[0.72, 0.48, 0.701351], Hue[0.0819199, 0.867387, 0.772079], Hue[0.565259, 0.534864, 0.782349], Hue[0.105818, 0.838710, 0.880722], Hue[0.89, 0.49, 0.647624], Hue[0.170899, 1., 0.586483], Hue[0.0284697, 0.767759, 0.915], Hue[0.621701, 0.528444, 0.85], Hue[0.02, 0.740259, 0.77]}], _ColorDataFunction, defaultcolors /@ Range[n], _String, PadRight[{}, n, ColorData[defaultcolors][#] & /@ Range[0., 1, 1/Max[1, (n - 1)]]], _Integer, PadRight[{}, n, ColorData[defaultcolors, "ColorList"]], _List, PadRight[{}, n, defaultcolors], _, PadRight[{}, n, defaultcolors & /@ Range[0., 1, 1/Max[1, (n - 1)]]]]; Options[HeisenbergGroupCayleyGraph] = SortBy[Join[Options[Graph], {ColorRules -> Automatic}], First]; HeisenbergGroupCayleyGraph[mod_Integer?Positive, opts : OptionsPattern[]] := Module[{edges, heisen3, vec, verts}, heisen3 = Sort[{{1, #1, #2}, {0, 1, #3}, {0, 0, 1}} & @@@ Tuples[Range[0, mod - 1], {3}]]; vec = Select[heisen3, Total[#, 2] == 4 &]; edges = Table[Union[ Table[Sort[{#[[1, 2]], #[[1, 3]], #[[2, 3]]} & /@ {he, Mod[he . v, mod]}], {he, heisen3}]], {v, vec}]; verts = Union[Flatten[edges, 2]]; Graph3D[verts, Flatten[MapThread[ Thread[Style[#1, #2]] &, {Apply[DirectedEdge, edges, {2}], expandColorRules[Length[edges], OptionValue[ColorRules]]}]], FilterRules[{opts}, Options[Graph3D]], VertexCoordinates -> verts]]; GraphicsRow[ Table[HeisenbergGroupCayleyGraph[n, ImageSize -> Large], {n, 2, 4}], ImageSize -> Large]

There are also groups known that yield growth intermediate between polynomial and exponential . There do not, however, appear to be groups that yield fractional-power growth, corresponding to finite but fractional dimension.

It is possible that one could view the evolution of one of our models as being directly analogous to the growth of the Cayley graph for a groupor at least somehow approximated by it. As we discussed above, the hypergraphs generated by most of our systems are not, however, uniform, in the sense that the structures of the neighborhoods around different points in the hypergraph can be different. But this does not mean that a Cayley graph could not provide a good (at least approximate) local model for a part of the hypergraph. And if this connection could be made, there might be useful results from modern geometric group theory that could be applied, for example in classifying different kinds of limiting behaviors of our systems.

On a sufficiently small scale, any manifold is defined to be like Euclidean space. But if one goes to a slightly larger scale, one needs to represent deviations from Euclidean space. And a convenient way to do this is again to consider model spaces. The most obvious is a sphere (or in general a hyperellipsoid)and this is what gives the notion of curvature. Quite what the appropriate analog even of this is in fractional dimensional space is not clear, but it would potentially be useful in studying our systems. And when there is a possibility for change in dimension as well as change in curvature, the situation is even less clear.