Cayley Graph Spectra and Expansion in Small Groups

ISEF Category: Mathematics

Subcategory: Algebra  ·  Difficulty: Advanced  ·  Setup: Home Setup  ·  Time: Full Year

The Hook

A tiny change in a graph can make information spread fast or slow. That is the whole game in expander graphs, and Cayley graphs give you a clean way to test it. You can use symmetry, eigenvalues, and group structure to see which generating sets spread best.

What Is It?

A Cayley graph turns a group into a network. Each group element becomes a node, and each generator tells you which nodes connect. If you change the generating set, you change the shape of the graph. That shape changes the graph spectrum, which is the list of eigenvalues from its adjacency matrix.

The second eigenvalue matters a lot. Think of it like a measure of how hard it is to trap flow in one part of the network. A smaller second eigenvalue usually means better expansion, so the graph mixes faster and resists bottlenecks. In this project, you study how twisted generating sets change that eigenvalue for small non-abelian groups, then look for patterns that stay optimal in a family such as PSL(2,p), which is a family of symmetry groups built from 2 by 2 matrices over finite fields.

Why This Is a Good Topic

This topic is a strong science fair choice because it is precise, testable, and rich in structure. You can compute spectra for many candidate generating sets, compare them, and then try to prove why one choice wins. It connects to real ideas in network design, error-correcting codes, and fast mixing algorithms. You also get a real math research skill set, including linear algebra, finite groups, and proof writing.

Research Questions

• How does changing the generating set alter the second eigenvalue of the Cayley graph for a fixed small non-abelian group?
• What is the effect of adding a twisted generator on the spectral gap compared with a standard symmetric generating set?
• Does the second eigenvalue stay minimal across all generating sets of the same size for a given group?
• To what extent do automorphisms of the group reduce the number of distinct generating sets you need to test?
• Which generating sets produce the best expansion for small PSL(2,p) examples with the same degree?
• How does the spectrum change when you compare a group and its quotient under related generating sets?

Basic Materials

• Laptop with Python installed.
• SageMath or another free computer algebra system.
• LibreOffice Calc or Google Sheets for organizing results.
• Reference notes on finite groups and matrix eigenvalues.
• Access to a graphing calculator or basic plotting tool.
• List of small non-abelian groups to test, such as dihedral, quaternion, and symmetric groups.

Advanced Materials

• Laptop with SageMath, GAP, or Mathematica if available through school or university access.
• Python with NumPy, SciPy, and NetworkX.
• Access to a linear algebra package for exact eigenvalues over algebraic number fields if needed.
• Research notes on PSL(2,p) and group representations.
• Optional access to a university mentor or faculty advisor for proof checking.

Software & Tools

• Python: Builds Cayley graphs, computes adjacency matrices, and automates eigenvalue checks.
• SageMath: Handles finite groups, matrix calculations, and exact algebraic computations.
• NetworkX: Helps you visualize graph structure and compare candidate generating sets.
• GAP: Computes group properties and lists generating sets for small groups.
• NumPy: Supports fast numerical linear algebra for spectral experiments.

Experiment Steps

1. Define the family of groups you will study and decide how you will encode each generating set.
2. Build a way to generate the Cayley graph and its adjacency matrix from group data.
3. Choose the spectral quantity you will compare, such as the second largest eigenvalue or spectral gap.
4. Create a search plan that tests standard and twisted generating sets without changing degree or group size.
5. Organize the results so you can compare symmetry, degree, and spectral behavior across many examples.
6. Formulate the strongest pattern as a conjecture, then test whether known group structure can support a proof.

Common Pitfalls

• Comparing generating sets with different sizes, which makes the eigenvalues hard to interpret fairly.
• Using only floating-point eigenvalues, which can hide exact ties or small differences in spectrum.
• Forgetting to account for isomorphic generating sets, which can make the same graph look like many results.
• Testing too few groups, which can make a pattern look universal when it only holds in one family.
• Skipping proof strategy early, which leaves you with data but no path to an optimality argument.

What Makes This Competitive

A strong version of this project goes past a numerical search. You would compare many generating sets under clear symmetry reductions, state a sharp conjecture, and connect the data to a proof idea. The best entries often use exact or symbolic calculations for small cases, then explain why the pattern should extend to a family like PSL(2,p). Careful controls and clean notation matter as much as the final result.

Project Variations

• Study how the same spectral question changes for dihedral, quaternion, or symmetric groups.
• Compare ordinary generating sets with inverse-closed generating sets to see how symmetry affects the spectrum.
• Test whether random generating sets or highly structured generating sets give better expansion for small groups.

Learn More

• MIT OpenCourseWare, Algebra II: Search the MIT OpenCourseWare site for finite groups and representation theory lectures that support Cayley graph work.
• NIST Digital Library of Mathematical Functions: Use this for background on eigenvalues, matrices, and related special-function references when needed.
• GAP system documentation: Search the official GAP documentation for finite group commands, Cayley graphs, and generator enumeration.
• SageMath documentation: Find tutorials on finite groups, graph construction, and eigenvalue computations in the SageMath docs.
• arXiv: Search for review papers on expander graphs, Cayley graphs, and PSL(2,p) spectral questions.
• MathSciNet or zbMATH: Use these databases through a school or library to locate peer-reviewed papers on expansion in finite groups.