As there's an algebra that generates the integers, there's one that generates the graph. It's a free monoid on an alphabet of six letters, one for each "face turn". But this is initially the pair of points over x = 1, this is where the alphabet lives. That is, you're free to generate words in the alphabet, call them algorithms, and iterate them. The closure of this algebra is the star of the alphabet, where "*" means zero or more iterations; clearly one iteration is the alphabet or words of length 1. The empty string is at (0,0), which we iterate freely (do nothing, that is) such that (0,0)* = (0,0).
Another version of the graph in #133 Please Register or Log in to view the hidden image! I'm calling it a graph move. What I did was disconnect the edge from (0,0), (1,2) and reconnect it as a loop on (1,1). But it represents the fact that \(gh = g^{-1} \). It's a dual representation and structure-preserving. So I can represent a metric distance "out of plane" as a loop. And I can take this graph (the other reduced graph is planar) to my cylinder with the points on a boundary. Graphically everything is nicely "on tile".
Another reduced graph with a 2-coloring. I'll let you work out what it represents. I've glued some points to the right boundary of a cylinder though. The colors are the ones that take h to (1,1) as a loop, and f as a vertical line to the graph's "upper" boundaries, that's the graph which here is a projection of a graph embedded in \( \mathbb Z^3 \) onto the Euclidean plane. Please Register or Log in to view the hidden image!
So a closer look at the consequences of deforming a planar graph, a presentation of a group, into a graph that "looks like" a presentation of another group, and that you need more than two dimensions to make it possible. Because the embedding in the graph locally "covers" six points, but globally only has four points in it (with three in the local space and one not in the local space, a G-set), the structure of the embedding (the symmetry of the graph which you have a privileged view of), appears to break at the point on the upper boundary at (4,8). This appears to be, algebraically, because \( T_Δ \) is translated over \( \mathbb E^2 \); the element (1,2) can't act more than 4 times, the 5th time it asserts itself globally and there's a locally symmetric action along (4,8), (5,9), so \( T_Δ \) appears to be able to "remember" this as it gets translated along the nice straight looking boundary (not included in the reduced version above). There's a lot more. This group has two identities, one acting on positions and one acting on orientations in the coset space--distinct because it means a change in the Schafli symbol for the tiling--a different coloring of the graph on the sphere.
So if you've been doing your homework, the notion of embedding elements of a group "in" a graph shouldn't be in the "I don't understand" basket. The graph (a choice of representation) has edges acting on edges (via composition such as gh), edges acting on vertices (g(0,1) = gf), and vertices acting on vertices ((0,0) + (1,2) = h), visually: Please Register or Log in to view the hidden image! This graph acts on itself locally to give the two (direction preserving!) derivatives \( g^n, h^n \): Please Register or Log in to view the hidden image! Please Register or Log in to view the hidden image! But hang on, if n is free (an iteration), then we actually have: \(g^* = g^n g^*, h^* = h^nh^* \).
And the last little detail that gives everything closure is that g acts on vertices in \( \mathbb Z^3 \). Meaning there is a copy of g in each dimension, notationally \( g \in \{g_x, g_y, g_z\} \), or I can use \( g \in \{g_1, g_2, g_3\} \), or \( g \in \{g_i, g_j, g_k\} \). Also the two derivatives above don't exist (except in the algebra) because the points (1,0), (0,1), (0,2) are disconnected components (hence only part of a local coordinate system, a kind of nullspace). such that if I iterate say, \( g_x \) at (0,0), I get the sequence (g(0,0), g(1,1), g(1,2), g(1,1)) or a 4-tuple, because g is locally a 4-cycle. To translate \( T_Δ \) (and so 'find' the action on the graph not just at (4,8)) I need to vary the index of g, like \( g_ig_j,\; i,j \in \{1,2,3\} \). And if you thought there was anything here speaking to finding a solution to the puzzle, it's the concept of walking through a graph. A solution or a partial solution is a walk that gets you closer to the origin.
It's a gauge "graph theory", for the following reasons. You first make a choice of a coordinate system for a subgraph--my tentatively or informally notated object <2,3>. This represents a choice of gauge for the object <2,2> reduced to the identity graph of \( \mathbb Z_4 \); you "gauge" \( \mathbb Z_4 \) in the way shown, by projecting one of its coordinates out of the plane a distance of 2. The distance is represented by the red-colored loop. The colors are just a way to visualise different objects (edges or vertices), and using the same color is then just a representation of the same scalar value in the overall algebra. The arrows on edges are auxiliary notation, they aren't really needed if edges are bi-directional (bi-linear?), but come in handy when you want to show the structure and direction of cycles so you can compare them.
So then, I at least can conclude that it's a given I can switch context from the graph of a group to a program algebra. Given since we're already there, that day arrived shortly after the original 3x3x3 puzzle appeared and mathematicians picked one up; the puzzle is physical, a kind of calculator (or single numeral in a much larger calculating device--i.e. a computer with an instruction set and branching operations, loops, a clock, "memory" and so on . . .). But that's obviously an abstraction--the sphere on the projective plane is not physical, has none of the above in it, they're all physical "objects", and projective space says nothing about computers, which are in this set. What about this free monoid? The set of letters in the alphabet are elements of a group, they have inverses, isn't the monoid a group, not a monoid? If you take the following subset of the complete alphabet: \( S = \{g_1, g_2, g_3\} \), then the first set product is \(S × S = \{g_1g_1, g_1g_2, g_1g_3, g_2g_1, ... , g_3g_3\} \). this is the first coset of G, the generator subgroup. The second coset is \( S × S × S = \{g_1g_1g_1, g_1g_1g_2, . . . , g_3g_3g_3\} \). And we find in the first coset that \( {g_i}^2 = h_i \), and in the second that \( {g_i}^3 = g_i^{-1} \) So the star of S is the free monoid acting on S. . . . in the third coset we find: \( {g_i}^4 = e \). The symbol e for the identity is the empty string in the monoid, and is the position identity "×" orientation identity (or one of the places these identities intersect), in the group. ed. . . "the star of S" should be: \( S^{×^{\ast}} \)
So far, everything has been about the permutation puzzle which is the so-called "Pocket Cube", or more loosely, the 2x2x2 stack in the shape of a cube, which algebraically corresponds to a subgroup of the full group of reflections of (2,2,2) triangles (subsets of Schwarz triangles) on the sphere (with or without the projective plane). What we see thanks to the coset graph is an external algebra: the free monoid acting on \( T_Δ \), or \( (T_Δ)^* \). The internal algebra is another free monoid \( S^* \). So what happens to either object when we take the stack to 3x3x3, or nxnxn? What about the other platonic tilings, such as the icosahedral (2,3,5) one? How do I describe the 3x3x3 cube puzzle in terms of a sphere? It's obvious by inspection that we have a type of composition of two G-sets in the 3x3x3 cube, one action is on the vertices, and one action is on the inner 'layers', since we can fix the vertex set and permute (not with the same degrees of freedom, however) those layers. So over each point in the 2x2x2 graph, or \( (T_Δ)^* \), we have all the permutations on the inner layers that leave the vertices (or elements in the 2x2x2 G-set) fixed such that their positions and orientations don't change. One way to characterise the extra elements the 3x3x3 puzzle has, is to make the vertex set blank (color them all the same), thus 'quotienting' the G-set with a "coloring action" that makes the elements of the 2x2x2 cube all algebraically equivalent (sending them to the identity permutation in G, or the empty string in \( S^* \)) . . . We then have an algebraic object with freely chosen colorings, another gauge freedom. So, it does seem that the approach I've used here can be extended to other triangle groups, and so to the external (graph-based) algebras of geometric permutation puzzles such as these: Please Register or Log in to view the hidden image!
There is one I suppose, quite important little detail I've left out all this time. Which is that the set of points in the object \( T_Δ \), is a partition of six points into two distinct sets, \( V_1, V_2 \). Since, for any bipartite graph \( G(V,E) \), G is connected (meaning there's a path between any pair of vertices in \( V_1 ∪ V_2 \)) and \( V_1 ∩ V_2 = ∅ \), and each edge in \(E\) connects an element of \( V_1\) to an element of \( V_2\). But since in \( T_Δ \), each of \( V_1, V_2 \) has isolated points the bipartite graph is not complete. It isn't technically the graph \(K_6 \) with 3 isolated vertices, but is the graph \( K_{3,3} \) with 3 isolated vertices. Notice in the completed graph of the group element f, there are two actions for f, one along each column of three points. So it looks like f has something to do with the partition of \(K_6 \); it all happens because of the choice of a coordinate system for \( T_Δ \). Not mentioned til now because it's something I should discuss with someone who knows what a bipartite graph is, then what not completing a bipartite graph means, and so on. /'stifles yawn'
The last couple of pages of my handout notes on graph theory, says this: 6. Graph colourings Def 6.1 A vertex colouring of the simple, connected graph G "=" (V,E) is an assignment of colours to the vertices in which no two adjacent vertices are coloured the same. We say G= (V,E) is k-colourable if it has a vertex colouring using k colours that has no two adjacent vertices coloured the same. Def 6.1.1 The chromatic number of G is k if G is k-colourable but not (k-1)-colourable. The chromatic number is written λ(G). Theorem 6.1 If the greatest degree of any vertex in the simple graph G is δ then G is (δ + 1) colourable. Theorem 6.2 (Brook) If G is a connected simple graph and is not a complete graph and if the greatest degree of any vertex in G is δ ≥ 3, then G is δ-colourable. while back in 5. Planarity ... Def 5.3 Two graphs H and K are homeomorphic (identical to within vertices of degree 2) if they can both be obtained from the same graph G by inserting new degree-2 vertices into E. If in a graph L we take an edge e = {u,v} and contract it by removing e and identifying u with v, so every edge incident with either u or v is now incident with "u.v", then (we have) the graph L' is the contraction of L. If G can be obtained from L by a sequence of contractions (removal of what amounts to an edge and a vertex), then we say G is the contraction of L.
Ok, the abstraction is that my pair of subgraphs, I'll post them a bit smaller here Please Register or Log in to view the hidden image! Please Register or Log in to view the hidden image! use three colours. If I colour the vertices instead there's a problem, because apart from (0,0) there are only two points. Aside from k-colourings, what about the contraction thing? Is the graph on the right a contraction? If I actually contract the loop to a point, does it colour the vertex at (1,1)?. I would say I'm not quite at a vertex k-colouring although I do know the greatest degree of any vertex.
The contraction, in the abstract, glues together two points in a \( \mathbb Z_4 \) graph, removing an edge with a weight of 2 from the complete graph and making pairs of edges weighted 1 into bidirectional edges (shown in the graphs of \( \mathbb Z_4 \) posted earlier). In \( T_Δ \) this edge is projected into \( \mathbb Z^3 \) from \( \mathbb Z^2 \). Removing the projection collapses \( T_Δ \) back to the plane; the red vertices in my large graph (the star of \( T_Δ \)) of 2 colours identifies where the contractions are. Another thing the colouring does is identify symmetry breaks (there are two places where a pair of green vertices are adjacent, for instance), and you can consider walks that are "properly" 2-coloured, following the above definition (for instance from (0,0) to (4,8) and back again). But of course, colouring is a free kind of action, I can choose any colouring from a (possibly infinite) set. I could introduce a basis for the generator set like \( G = \{g_a, g_b, g_c\} \), where a,b,c are fixed colours (ones that don't change, heh), say, red, green, and blue. I can then take 3-coloured walks, each vertex is a different color since iterating any single generator leaves me "on tile", in the rotation group of a square, or "with a \( \mathbb Z_4 \) action" on vertices. Moreover, the total 'lifting' of the graph on the red vertices into a third dimension is now a kind of sum over vertices, I guess I can at least count them.
Please Register or Log in to view the hidden image! This complete graph is variously a mnemonic device, a map of the relations between the opposite faces of a cube when four of eight vertices are rotated while the remainder are fixed, four roots of unity in an adjacency graph, etc. If you project the planar graph into a third dimension by lifting the red vertex into it so the three blue ones stay on tile, it's a pre-geometric embedding (the graph has no angles defined anywhere, distance is affine, there are only weightings). It's an abstraction. I say "on tile" instead of "stay planar" because a tile is a thing embedded in a locally flat region, maybe it's the surface of a sphere or a torus.
Another look at the integers and what the free generation thing means. It's kind of trivial to see that the integers \( \mathbb Z \) along the real line have a "generating set", the set {-1,1} under addition. So mathematically, \( \mathbb Z \) is generated by freely adding elements of the set {-1,1} to itself. "Is generated" implies "will be generated" and "has been generated". Mathematics of course, isn't concerned about "when" things are true temporally, but logically. So you say the integers are freely generated "when" addition acts freely on the generating set, which of course it always has done. So you can embed graphs in \( \mathbb Z^n \) and "un-embed" them, so that no integers are harmed. You can peel a graph off a surface, transform it and put it back, if you want to; what the result might be depends on what else you've defined, maybe whether you keep some copies, as weightings, of certain integers in your graph, etc. You're free to do whatever you like, it's a graph so it doesn't care . . . But you can't futz with the ordering of \( \mathbb Z \), this is fixed, an invariant (possibly the universe might collapse around you if you did manage it).
Here's another abstraction I use sometimes: With the "free" \( \mathbb Z_4\)-action in the face-turn metric, you can rotate one of the six faces of the Pocket Cube puzzle as often as you want to. But the vertices are adjacent in one of four places as you do this; ignoring the physics of what's involved in applying torque to half the puzzle, there are four places "under rotation" that the vertices are adjacent, graph-theoretically. So the abstraction of this is that you have a nice smooth hill in front of you, a symmetric surface. You can choose to go around the hill in one of two directions (say, to the left or to the right). When you get to the other side, opposite the point you started, you forget which direction your path took; in fact as far as you're concerned you went straight over the hill. Otherwise you can go halfway around the hill, if you want to remember which direction you take. Then you see your path is "contracted" through this hill (although you can also choose to keep going and forget the direction); you can transport yourself through the hill (this is however, a physical action in the puzzle, a rotation of 180°); whether you choose to consider this transport as being "instantaneous", or "going around a really small loop" is a matter of . . . choice. But emerging from inside the hill you just "tunneled" through, you find you've been reflected and are now the inverse of yourself (if you're a group element). This kind of comports with algorithmic notions, and that the cube in a "solved" state is the union of all the words in the free monoid that send permutations to the identity "instantaneously"; you can choose this kind of model without breaking any laws of mathematics, although you can't use it physically. Then the conserved information in this algorithmic model is direction of rotation in each local frame of reference (the bipartite graph on each tile). Clearly the graph indicates \( S_4 \) permutation symmetry is conserved since the (0,0)-(4,8) boundary is "filled" with all 24 group elements. This looks like a conservation of \( \mathbb Z_6 \) symmetry via the embedding of \( \mathbb Z_4\) in its bipartite graph.
And note too that this particular graph, based on a particular tiling, is the shallow end; the graphs for other tilings with more permutations go a lot deeper (for example there are about 4 quintillion permutations in the 3x3x3 Rubik's cube, a much larger number than a mere 3.7 million). Just a squiz at these tilings suggests this: Please Register or Log in to view the hidden image! Each tiling is also a graph. You can walk from face to face in any of these graphs and the walk is a 2-coloured graph. But consider what reflecting a pair of coloured faces does (a transposition of faces). In the (2,2,2) tiling, if you reflect each of the four tiles on the upper hemisphere to the left or right you get the same object, a sphere with a 2-colouring of 4 quadrants. This is clearly equivalent to rotating the upper hemisphere by 90° in either direction. To "store" the direction information, use more than two colours in the graph.
Now I can, for the sake of those still concerned about who is allowed to use the word "tensor": The underlying permutation space (i.e. all 3.7 million of them), has an algebra which is an algebra of permutation matrices. Take any element of \( S_4 \), the symmetric group on 4 letters, as a 0-1 permutation matrix; a 4x4 matrix of 1s and 0s, such that each row has a single 1 and each column has a single 1 in it (that is, the sum over a row or column is 1, the unit). Now make this 4x4 matrix into a 8x8 matrix; tensor your choice of element with \( I_2 \in S_4\). You can do this with any member in the G-set of 4x4 matrices if they're in \( S_4 \), the matrix product (whereby each 1 in the left matrix is replaced by the matrix on the right), "is" the tensor product (which now has row and column indices), as an element of \( S_8 \). You can rewrite a 4x4 permutation matrix (which if it is a permutation matrix, must be in \( S_4 \)), as a sum of partial permutation matrices (actually any nxm matrix can be written as a sum this way, even a 0-matrix), it turns out you then have a tensor algebra with a 4-dimensional basis: the four 2x2 0-1 matrices each with a single 1 and three 0s in it. These I've dubbed the set of projections, but they have a few other names. Moreover, the 2x2 basis under multiplication is a semigroup, a monoid is a semigroup with an identity. This is the set of projections (projectors, I guess, if one uses them as operators): \( \biggl\{\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix},\,\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix},\,\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix},\,\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\biggr\} \).
Sorry mistake, the above should read "tensor your choice of element with \( I_2 \in S_2 \)". Say you choose \( I_4 \in S_4 \) as the left matrix, then you have \( I_4 \otimes I_2 = I_8 \in S_8 \). The set of tensor products \( S_4 \otimes I_2 \) are all the orientation-preserving elements of \( S_8 \), acting on a tiling of the 2-sphere.
Tsk, more shoddiness. I shouldn't really use the "×" symbol to define cosets. You don't get sets of ordered pairs ("×" is conventionally the Cartesian product, here acting on sets), you get sets of concatenated letters. Indeed, concatenation is the bog-standard operation for monoids; so formally I should define an operation on two sets which concatenates an element from one set with another element from the other set (this is implied by \( g_ig_j . . . \) in the earlier version). So again consulting some course material (lecture notes on Finite Automata, no less) Def 1.7 (i) For R and S, both sets, we define the set product R·S: \( R·S = \{ rs : r \in R, s \in S\} \) (ii) If R = S, then: \( S^0 = \{\lambda\} = \Lambda \) \( S^1 = S \) \( S^2 = S·S \) \( S^{k+1} = S^k·S \) . . . this: \( \{\lambda\} = \Lambda \), means the set \( \Lambda \) containing the empty string \( \lambda \). So we have that \( S^* = S^0 ∪\, S^1 ∪ \,S^2 \,∪\, . . . ∪\, S^k\, ∪ \,. . . = \bigcup_{k=0}^{\infty} S^k\)
