So, I’ve been gone for a while with school and work, but I’ve found some spare time and I wanted to bring to your attention an amazing connection between group theory: the study of abstract collections of objects and how they interact with when combined, and graph theory: the study of sets with an irreflexive relation R. Hopefully this will be the first of many posts to come this summer :)

A group is a set which is acted on by an operation. This operation takes two elements and combines them to make a third. There are some rules (Axioms) for the combining of elements, the first being that the combination of any two elements in the set creates another element that is in the set. This is called closure, and is very important. Another rule related to this one is that every element is required to have an inverse in the set, which gives us our next rule, that all groups require exactly one element that acts like the number 1 does for multiplication. Whenever anything is combined with this identity element, we get the other number back (x*1=x). the one thing that’s missing from this definition is the associative property; the idea that (x*y)*z=x*(y*z). This obviously isn’t the end of it, but we’ll come back to this later.

Graphs are pretty cool as well. They are part of model theory (so are groups for that matter), and are used to describe situations in either a visual or abstract way.To get a graph, we take a finite nonempty set V and construct a relationship between the elements of V called R this relationship is symmetric, meaning if (u,v) is in R, then (v,u) is in R. We denote E the set of subsets of R that include all symmetric elements. If V is {a,b,c,d}, then R is {(a,b), (a,c), (a,d), (b,c), (b,d), (c,d), (d,c), (d,b), (d,a), (c,b), (c,a), (b,a)}, and E is {{(a,b), (b,a)}, {(a,c), (c,a)}, {(a,d), (d,a)}, {(b,c), (c,d)}, {(b,d), (d,b)}, {(c,d), (d,c)}}. The letters correspond to their functions, V is the set of vertices, the the generator elements, R is the set of all possible lines (Relationships) that can be drawn between the vertices, and E is the set of all edges on the graph. For any graph G, we call V the vertex set, and call E the edge set. The order of a graph is the number of elements in V, and the size is the number of elements in E. We denote the vertex set of G as V(G) and the edge set as E(G). All graphs have to have Vertices by definition, but not all graphs have to have edge sets that contain elements, which is interesting.

Here are some graphs!

How do we relate the two? Well, groups originally arose out of the study of permutations. Permutations are a kind of homomorphism called an automorphism, which is a bijective function from a set to the same set. Every group is isomorphic to a group of permutations by the application of Cayley’s theorem.

Let’s say we have a graph G of order p, and V(G)={a_1, a_2, a_3… a_p}. If we create an isomorphism, say B:V(G)→V(G) such that B(a_i)=a_i for i=1,2,3,…p. This is just the identity permutation, but other automorphisms exist which correspond to other permutations. Under the operation of simple combination of permutations, these automorphisms form a group supremely denoted “the group of G” and given the symbol A(G). To get a feel for this, consider a straight line with endpoints 1 and 3, with a third point 2 between them. Taking a permutations implies renaming the points in a way which yields the same kind of relationship. Since 1 is connected to 2, 1 needs to remain connected to 2, and likewise for 3. The only other permutation that makes sense is the permutation which exchanges the places of 1 and 3. So, we get the permutations {1,2,3}→{1,2,3} and {1,2,3]→{3,2,1}. These two form a group together under combination, and are the group of G if V(G)={1,2,3} and E(G)= {{(1,2),(2,1)}, {(2,3), (3,2)}}. Both the vertex and edge set work together to produce the group A(G).

It’s interesting to wonder if because edges and vertices are the objects which define A(G) that the symmetry group of a graph laid out in some efficient way has anything to do with A(G). It actually does, and you can read all about it here (This actually surprised me a little)!

The other way that group theory is related to graph theory is again through Cayley ~~It’s almost like he was important or something~~. Groups can be thought of in terms of elements called generators. Generator elements can generate other elements in the group through successive combination with themselves, hence their name. If there is one generator the group is called cyclic because beginning at the identity element, after some number of combinations with the generator you arrive back at the identity element. You can have a group with more than one generator as well, in fact, here’s one

This one is in terms of what looks like rho (the P thing) and phi (the loopy thing). When you have generators like this, they often follow rules. For the one above, we can see that rho cubed never appears and that rho times rho squared is equal to the the identity element, so we can conclude that rho cubed is equal to the identity element. We also see that phi times phi is equal to the identity element, so phi squared is equal to the identity element as well. That’s all well and good, but can you prove that all groups can be written in terms of some number of generators (and not just the trivial one with all elements of G included)? I’ll do another post on that, but to bring this back to graph theory, I need to introduce cayley diagrams, which are a great way to come up with new groups!

This is a simple Cayley diagram (the one from the group shown before with a equal to phi, b equal to rho, and rho times phi equal to a times b squared). From the picture, you can see that the solid arrow means multiply by b, and the dashed arrow means multiply by a; you are allowed to add more types of arrows when you have more than two generators. An arrow head is used to show the direction of multiplication (which is always assumed to occur on the right side) unless the element is equal to its own inverse, which is the case with a, when a simple line is used.

How are these related to graphs? Each vertex represents a new element of G, so let V(G)={e,a,b,b^{2},ab,ab^{2}}, and E(G) be equal to the set of all elements that are connected by a single straight line. You’ve now turned a set into a graph, and can now commence doing graphy things to it!

These are just a few ways that group and graph theory are related, I didn’t even go into coloring theorems, topology, or Graph matrix theory. It’s interesting to think that it’s connections like this that have allowed us to make major breakthroughs in mathematics. Problems which seemed impossible in one theory have be translated over in a sense to problems in another area where they were more easily accessible. One immediate example comes to mind with the proof of the Taniyama-Shimura Conjecture by Andrew Wiles which proved Fermat’s Last Theorem. The problem aimed to connect two areas of mathematics, modular forms and elliptic curves, and in turn made a statement more accessible in number theory of all places.

All mathematics is related somehow, you just have to find the right bridge. Happy Proofing :)