Jul 17, 2024  
2022-2023 Academic Catalog 
2022-2023 Academic Catalog [ARCHIVED CATALOG]

MAT 322-01 & 02 - Advanced Topics in Algebra: Algebraic Graph Theory

4 credits (Spring)

While the resemblances between graph theory and algebra initially appear limited, the exchange of ideas between these two fields has been mutually advantageous. Using ideas from algebra, one can construct graphs with special properties. For example, Paley graphs arise by taking the orbit of a single edge under the semilinear automorphisms of a finite field. Many important graphs can be described and studied by recognizing them as Cayley graphs of groups with a set of generators.

Studying the eigenvalues of the adjacency matrix of a graph leads to spectral graph theory, which has yielded beautiful structural results about graphs, as well as practical applications.  Spectral graph theory is at the heart of Google’s PageRank algorithm and has begun to yield potential advances in augmented reality.

Graph theorists not only benefit from making use of algebra, but also return the favor.  Some problems in group theory have been solved by reducing them to problems in graph theory, or have found examples of remarkable groups arising from graphs.  Most notably, in the monumental efforts of the late 20th century to classify the finite simple groups, several of the examples (such as J2, HS, and McL) were constructed by studying subgroups of the automorphism groups of certain remarkable graphs.

In the first half of this course, students will be introduced to some of the ideas at the intersection of algebra and graph theory.  In the second half, students will work on an independent research project on a specialized topic within the subject, to be determined by the student in consultation with the professor.

Prerequisite: MAT 321 
Instructor: C. French