The Cylinder and the Moebius strip are a nice paradigm because the classical algebraic topology elements are the same for it: they are both homotopic to the circle, their cohomologies agree, their fundamental groups agree. Their metric properties like diameter or systoles agree (if implemented properly of course). Their main difference is that the Moebius strip has a boundary with one component while the cylinder has a boundary with two components. The Moebius strip is also not orientable. A fancy way to see the difference is to see the Moebius strip as a non-trivial fiber bundle over the circle, while the cylinder is a trivial fiber bundle. A cohomology that distinguishes the Moebius strip and the Cylinder obviously must be of more “topological” and not “homotopy” nature. Quadratic cohomology does this. Quadratic cohomology changes in general if one makes a homotopy deformation. It is preserved by homeomorphisms although. But homeomorphisms are a bit trickier to define in the discrete. Obviously homeomorphisms preserve dimension and manifold structures. In differential geometry classes like this, I defined a homeomorphism in the discrete through connected sum constructions: take a unit ball and replace it with an other ball of the same dimension. A n-ball is a n-manifold with boundary such that its boundary is a (n-1) sphere and a (n-1) sphere. Such steps do not change the quadratic cohomology so that quadratic cohomology is invariant under homeomorphisms. It is not invariant under more relaxed transformations. Especially, dimension needs to be invariant.
This spring we have looked at game graphs. The entire project has started when a group of students had contacted me about a project suggesting a topic in the intersection of games, graphs and groups. It is a perfect topic because game theory itself (at least part of it) is too ambiguous in its foundation, at least for mathematicians. There are many approaches trying to axiomatize it. Zermelo’s ground breaking paper on games would today of course only be acceptable as a blog post and not as a research paper. The axiomatic foundation of von Neumann and Morgenstern also have formalisms which hardly can be used when playing a solitaire or chess game. Other formalisms like Arenas have been developed. Many work on “game trees”. Classical textbooks prove Zermelo’s theorem by working on trees. This is a bit silly as most of the games we consider like chess or go, or solitaire games like the Rubik are not trees. They are graphs in which closed loops can occur. One can always get from a graph a tree by looking at the self-avoiding walk tree from a vertex but this is not how we think about things when playing games. So, the idea of my students to look at things in a purely graph theoretical way is refreshing. One can formulate a relatively small and intuitive system of axioms which also settle terms like “strategy” nicely. Mathematically inclined textbooks either define it as a definite rule which tells what to do in any given situation, or then probabilistically by putting a probability measure on the set of all possible moves. The first one is too restrictive , the second one leads to different questions and threorems like the beautiful minimax theorem of von Neumann in 1928, which Nash beautifully proved using the Brouwer fixed point theorem. Nash also led the foundation to prove the Brouwer fixed point theorem game theoretically (he did not do that himself) but it happened in 1979 with David Gale. Gale had looked at variants of Hex also in the late 1950ies. Anyway the graph theoretic setup is small and and can be understood. We have a write-up here. (73 pages PDF at the moment).
Lets look at the cylinder and Moebius strip. It is a popular research problem to take any graph and look at its game graph G, in which is the Cayley graph of the permutation group of the vertices in which the edges define transpositions. The “folklore theorem” (a theorem everybody seems to know but nobody seems to prove because it is too easy, we gave a proof in our project however), tells that if the initial graph is connected, then the game graph covers the entire symmetric group. It is quite obvious if you think about it but for anybody who has played with the 15 puzzle, it is still not so obvious because there could be some kind of parity that is preserved. The game graph of sliding puzzles are not Cayley graphs however so that for sliding puzzles the possibilities are more rich as Wilson’s theorem tells. There is an exceptional case PGL(2,5) for example. For 1-connected graphs the graph is small (as we can not park stuff…), for circles it is the cyclic group, for bipartite graph cases, it can be the alternating group. Otherwise it is the symmetric group. Anyway, for the Cylinder and Moebius strip, in the transposition case we get Cayley graphs that have the same number of vertices 8! and the same number of edges (as the vertex degree is 15, it is 8!*15/2 = 302400 by the Euler Handshake formula (which sometimes is called (silly) the fundamental theorem of graph theory. Well, it is a Gauss-Bonnet formula for a specific valuation, E(G) = f_1, the number of edges is a valuation and every valuation has a Gauss-Bonnet formula and in this case the curvature is half the vertex degree …
Anyway, when looking at the diameter of these two game graphs, they are different. Some of the students got into the BFS (breath-first-search) business and looked at the BFS layer sizes. This is for me personally very interesting as BFS layers are nothing than “wave fronts” and we were especially since 2025 obsessed with wave fronts in differential geometry. Wave fronts are very interesting metric quantities. One looks at the size of the vertices in a graph that have distance r from the point. Everybody who has played games is interested in such numbers. How many moves are needed to get from one position v to an other position w. What is the worst case? It is obviously also of interest in computer science (maybe almost a fetish…) Well it is important deservedly so because in the case of Cayley graphs,l we can use the BFS layers to compute the diameter of the graph, without actually constructing the graph. Some of the students looked at the problem whether the BFS layer graph is always convex down. As I told in the video, this was hard to crack. We caved in eventually and gave it toan AI overlord. The world at the moment worships these gods, but we have to wait until the backlash comes (just look at the Spielberg movie AI.) I myself found it deeply troubling that we could ask a machine to get us an example of a game graph for which the BFS layer graph is not concave down and that it found one! I mentioned in the youtube video also that the AI’s become more arrogant. It starts to display self-confidence and arrogance one previously has only known in academia. But it still tries hard to please the customer. Wait until the customers are no more needed….
There is an other story one could tell here. When making the measurements of the size of a Cayley graph, one can use different tools. The BFS layers have sizes {0, 16, 137, 781, 3038, 7818, 12375, 10845, 4581, 700, 28, 0} for the Moebius strip and {0, 16, 136, 784, 3104, 8008, 12480, 10606, 4383, 744, 56, 2, 0} for the cylinder. Here is the mathematica computation of the game graph and computing its diameter: The procedure is a bit faster than what we have done before (see below for the much fast er BFS computation, which is the same thing in Cayley graph situations, (not in more general cases however, like sliding puzzles.)
moebius =UndirectedGraph[Graph[{1->2,2->3,3->4,4->5,5->6,6->7,7->8,8->1,1->5,5->2,2->6,6->3,3->7,7->4,4->8,8->5}]];
cylinder=UndirectedGraph[Graph[{1->2,2->3,3->4,4->1,5->6,6->7,7->8,8->5,1->5,5->2,2->6,6->3,3->7,7->4,4->8,8->1}]];
T[a_,X_]:=Module[{b=a}, b[[X[[1]]]]=a[[X[[2]]]]; b[[X[[2]]]]=a[[X[[1]]]]; b];
GameGraph[gamma_]:=Module[{e=EdgeList[gamma],v=VertexList[gamma],A,B,K},n=Length[v];A=Permutations[v];K=Length[A];
B=Table[a=A[[k]];b=T[a,e[[l]]];a->b,{l,Length[e]},{k,K}]; B=Union[Flatten[B]]; UndirectedGraph[Graph[B]]];
G1=GameGraph[moebius]; GraphDiameter[G1] (* a graph with |V|=40320, |E|=322560 and diameter 10 *)
G2=GameGraph[cylinder]; GraphDiameter[G2] (* a graph with |V|=40320, |E|=322560 and diameter 11 *)And now lets look at the faster BFS computation
moebius =UndirectedGraph[Graph[{1->2,2->3,3->4,4->5,5->6,6->7,7->8,8->1,1->5,5->2,2->6,6->3,3->7,7->4,4->8,8->5}]];
cylinder=UndirectedGraph[Graph[{1->2,2->3,3->4,4->1,5->6,6->7,7->8,8->5,1->5,5->2,2->6,6->3,3->7,7->4,4->8,8->1}]];
T[a_,X_]:=Module[{b=a}, b[[X[[1]]]]=a[[X[[2]]]]; b[[X[[2]]]]=a[[X[[1]]]]; b];
BFS[gamma_]:=Module[{e=EdgeList[gamma],v=VertexList[gamma],A,A0,A1,L},
e=EdgeList[gamma]; v=VertexList[gamma]; L={0}; n=Length[v]; A0={Range[n]}; A=A0; While[Length[A0]>0,
A1=Flatten[Table[T[A0[[k]],e[[l]]],{l,Length[e]},{k,Length[A0]}],1]; A1=Complement[A1,A]; A=Union[A,A1]; A0=A1;
L=Append[L,Length[A1]] ]; L ];
{BFS[moebius],BFS[cylinder]}And now lets look at the GAP code, which produces the same result:
LoadPackage("grape"); # we use the moebius strip
a:=(1,2); b:=(2,3); c:=(3,4); d:=(4,5); e:=(5,6); f:=(6,7); g:=(7,8); h:=(8,1);
i:=(1,5); j:=(5,2); k:=(2,6); l:=(6,3); m:=(3,7); n:=(7,4); o:=(4,8); p:=(8,5);
G:= Group(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p);
S:=GeneratorsOfGroup(G); C:=CayleyGraph(G,S);; Diameter(C); # 10
a:=(1,2);b:=(2,3);c:=(3,4);d:=(4,1);e:=(5,6);f:=(6,7);g:=(7,8);h:=(8,5);
i:=(1,5);j:=(5,2);k:=(2,6);l:=(6,3);m:=(3,7);n:=(7,4);o:=(4,8);p:=(8,1);
G:= Group(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p);
S:=GeneratorsOfGroup(G); C:=CayleyGraph(G,S);; Diameter(C); # 11