Cayley Graphs

Arthur Cayley

August 16, 1821-January 26, 1895

Abstract Definitions and Concrete Pictures

Robert “Dr. Bob” Gardner

ETSU Abstract Algebra Club

Fall 2024

Primary References

Introduction to Modern Algebra 1 and 2

Intro. Modern Algebra (Maybe)

Graph Theory 1 and 2

Graph Theory Supplement

Niccolò Tartaglia (1500-1557) and Ludovico Ferrari (1522-1565)

The Early History of Group Concepts 1

Joseph-Louis Lagrange, in the early 1770s set out to understand why equations of third and fourth degree equations have formulas for solutions. He realized that a “key object” in the reason was the group of permutations of the roots.

Joseph-Louis Lagrange (1736-1813)

The Early History of Group Concepts 2

In 1799, Paola Ruffini gave a several hundred page “proof” of the impossibility of solving a 5^th degree polynomial (and higher) with an algebraic formula. Unfortunately, gaps have been found in Ruffini’s proof (though his result is correct).

​

​

Paolo Ruffini (1765-1822)

He was the first to explore several group theory results in the setting of permutation groups, including the order of an element, conjugacy, and cycle decomposition of permutations. He did not define a group (or even a permutation group).

Abel and the (Algebraic) Unsolvability of the Quintic

Groups (rings and fields) became part of algebra in the 19^th century. While look-ing for an algebraic formula for the zeros of an n^th degree polynomial, Abel showed that there is not (in general) an algebraic solution to a 5^th degree (or higher) polynomial equation. These conditions involved permutations of the zeros of the polynomial and a key part of his proof is based on commutativity (that’s why we call commutative groups “Abelian”).

Niels Henrik Abel

(1802-1829)

Galois and the Classification of Solvable Equations

Evariste Galois

(1811-1832)

Galois gave conditions for the existence of an algebraic solution of a general n^th degree polynomial equation (the condition is that the Galois group of the equation must be “solvable”). The permutations of the zeros of a polynomial in the study of algebraic equations led in the 19^th century to the more abstract study of groups in general and permutation groups in particular.

Cayley Defines a “Group”

Arthur Cayley gave the first definition of a group in 1854.

(page 41)

The Early History of Group Theory

In his 1854 paper, Cayley gave tables for several groups and described groups of matrices. He described groups of orders 4, 6, 18, and 27.

The first two complete Cayley Tables ever published

Definition of Group

Examples of Groups

Cayley Explores a Group Theory Problem

Cayley published two papers on group theory in 1878. These were follow-ups to his 1854 paper.

A. Cayley, Desiderata and Suggestions: No. 1. The Theory of Groups, American Journal of Mathematics, 1(1), 50-52 (1878)

​

A. Cayley, Desiderata and Suggestions: No. 2. The Theory of Groups: Graphical Representation, American Journal of Mathematics, 1(2), 174-176 (1878).

Cayley Introduces Cayley Graphs/Digraphs

But what does this mean?

Fraleigh Discusses Cayley Digraphs

Fraleigh uses arcs (and edges) to represent MULTIPLICATION ON THE RIGHT!

A Standard Here:

Gallian’s Definition of a Cayley Digraphs

Gallian uses arcs (and edges) to represent MULTIPLICATION ON THE RIGHT!

1

2

3

Permutations

Permutations

1

3

2

Permutations

1

3

2

Permutations

1

3

2

We find that the multiplication table for the group of symmetries of an equilateral triangle is:

Notice that it contains a subgroup or order 3.

Writing Elements in terms of Generators

Bondy and Murty Define Cayley Graphs in an Exercise

Bondy and Murty use edges to represent MULTIPLICATION ON THE LEFT!

Godsil and Royle’s Definition of a Cayley Graph

Godsil and Royle use edges to represent MULTIPLICATION ON THE LEFT!

A Cayley Graph

Godsil and Royle’s Definition of a Cayley Digraph

Godsil and Royle use edges and arcs to represent MULTIPLICATION ON THE LEFT!

Notice that this Cayley Digraph is different from the previous one!

​

Remember Cayley’s Original Digraph?

A. Cayley, Desiderata and Suggestions: No. 2. The Theory of Groups: Graphical Representation, American Journal of Mathematics, 1(2), 174-176 (1878).

Based on Schaum’s Outline of Theory and Problems of Group Theory by Benjamin Baumslag and Bruce Chandler, NY: McGraw-Hill (1968).

Back to Cayley’s Second 1878 Paper

A Cleaner Drawing of the First Cayley Digraph

A. Cayley, Desiderata and Suggestions: No. 2. The Theory of Groups: Graphical Representation, American Journal of Mathematics, 1(2), 174-176 (1878).

Theorem 1 “Picture Proof”

…

Theorem 1 “Picture Proof” (continued)

…

What Can a Group Tell us about a Cayley Graph?

Can We Recognize a Graph as a Cayley Graph?

So a graph that does not contain a Hamiltonian path is not a Cayley graph of a finite abelian group.

Definition. A Hamiltonian path in a graph is a path (i.e., a sequence of consecutively adjacent distinct vertices) that includes all vertices of the graph.

A Cayley Graph Isomorphism Result

Theorem 5. Every finite group is the automorphism group of some finite graph.

Some Graph Automorphism Results

Definition. An automorphism of a graph is an isomorphism of a graph with itself.

Theorem 5 is due to Robert Frucht (1939), and the proof is based a Cayley graph of the given group!

Theorem 5. Every finite group is the automorphism group of some finite graph.

Some Graph Automorphism Results 2

Wait! EVERY FINITE GROUP?

That means we can draw PICTURES of groups!!! I pictures…

…with some “additions”

Based on “Automorphism Group of Graphs (Supplemental Material for Intro to Graph Theory),” R.B. Beeler (2018).

Conclusion

1. Truncated octahedral graph on first slide: https://mathworld.wolfram.com/CayleyGraph.html
2. Cayley’s two 1878 papers: https://www.jstor.org/stable/pdf/2369433.pdf and https://www.jstor.org/stable/pdf/2369306.pdf
3. Image of Ferrari from: https://www.youtube.com/watch?v=iRnkSJSVOmo
4. Images of Lagrange and Ruffini: https://en.wikipedia.org/wiki/History_of_group_theory
5. “Automorphism Group of Graphs (Supplemental Material for Intro to Graph Theory),” R.B. Beeler (2018): https://faculty.etsu.edu/beelerr/automorph-supp.pdf

​

References and Sources

Websites

1. J.B. Fraleigh, N.E. Brand, A First Course in Abstract Algebra, 8^th edition (Pearson, 2021).
2. J.A. Gallian, Contemporary Abstract Algebra, 8^th edition (Brooks/Cole, 2013).
3. C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics #207 (Springer, 2001).
4. J.A. Bondy and U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics #244 (Springer, 2008).

​

References and Sources

Books

Happy Halloween!

The ending slide from Young Frankenstein (Mel Brooks, 1974)