# Applications of graph theory to algebra?

Seeing as graphs model relations and algebra is essentially entirely based on relations, one would think that the two fields would inform each other. I know that algebra has many applications to graph theory, but what about applications of graph theory in algebra? Lattice theory, category theory, whatever.

• Cayley graphs are apparently objects of interest in group theory. However, I have no further information to give on this front, as I have myself been fruitless in my efforts to find out why. – A.Sh Feb 18 '16 at 11:40

The Amitsur Levitzki theorem can be proven using Euler trails. There's a statement of the theorem and a proof in my blog.

Based on nothing more than a vague knowledge of these subjects' existence and the power of Wikipedia, I came up with two. Since these aren't topics I've studied much, I can't say for sure how much actual graph theory is involved. But I can vouch for the fact that graphs seem to be commonly used tools, at the very least for advertising the field to grad students.

Geometric Group Theory

Another important idea in geometric group theory is to consider finitely generated groups themselves as geometric objects. This is usually done by studying the Cayley graphs [...] endowed with the structure of a metric space, given by the so-called word metric.

Bass-Serre Theory

The theory relates group actions on trees with decomposing groups as iterated applications of [algebra things], via the notion of the fundamental group of a graph of groups.

Let $G$ be a group and $H$ be a finite index subgroup of $G$. Say $|G:H|=n$. There there exists elements $g_1, \ldots, g_n\in G$ such that the set $\{g_1, \ldots, g_n\}$ forms a set of representatives of all the left cosets of $H$ in $G$ as well as the set of all the right cosets of $H$ in $G$ simultaneously.

This fact has an algebraic proof but it can be neatly proved using the Hall's Matching Theorem (a.k.a the marriage theorem).

• $H$ can be either a finite indes subgroup or a finite subgroup of $G.$ – bof Feb 18 '16 at 7:41
• @bof I didn't know that the result is true for finite subgroups too. Can you please outline proof? – caffeinemachine Feb 18 '16 at 7:47
• Instead of trying to cram a proof outline into a comment, I give a reference: Theorem 10.1.6 on p. 171 of L. Mirsky, Transversal Theory, Academic Press, 1971. "Let $H$ be a finite subgroup of an arbitrary group $G.$ Then the family of left cosets of $H$ and that of right cosets of $H$ possess a common transversal." – bof Feb 18 '16 at 8:07
• @bof I have a truly marvelous demonstration of this proposition which this margin is too narrow to contain. Fixed that for you! :P – stackErr Feb 18 '16 at 16:47

Some methods for solving huge sparse system of linear equations use some graph theory.

Try searching the Internet for "system of linear equations" and "strong connected component". The idea is to break the task into smaller (if possible) before applying traditional algebraic methods.