12. Pseudorandom graphs II: second eigenvalue

TL;DR

The Alon-Boppana bound determines the minimum value of lambda (the second largest eigenvalue of a graph) in an n, d, lambda graph, showing the relationship between eigenvalues and pseudorandomness in Cayley graphs.

Transcript

YUFEI ZHAO: All right. Last time we started talking about pseudorandom graphs, and we considered this theorem of Chung, Graham, and Wilson, which, for dense graphs, gave several equivalent notions of quasi-randomness that, at least the phase values, do not appear to be all that equivalent. But they are actually-- you can deduce one from the other. ... Read More

Key Insights

• 💐 The Alon-Boppana bound determines the lower bound for the second largest eigenvalue in a graph.
• 🎁 Two different proofs of the Alon-Boppana bound were presented, demonstrating the relationship between eigenvalues and pseudorandomness.
• 😚 The trace method involves counting closed walks in a graph and provides a way to estimate eigenvalues.
• 🌲 The eigenvalues of a graph can be related to the spectral radius of an infinite d-regular tree.

Questions & Answers

Q: What is the Alon-Boppana bound?

The Alon-Boppana bound determines the minimum value of the second largest eigenvalue (lambda) in an n, d, lambda graph, showing the relationship between eigenvalues and pseudorandomness in Cayley graphs.

Q: How is the Alon-Boppana bound proven?

Two different proofs were presented: one using Grothendieck's inequality and one using the trace method. The proofs exhibit vectors with specific properties to bound the eigenvalues.

Q: What is the trace method?

The trace method involves counting closed walks in a graph. By considering closed walks on an infinite d-regular tree, lower bounds on eigenvalues can be obtained.

Q: Are there graphs that achieve the Alon-Boppana bound?

Yes, there are graphs for which the eigenvalues are close to the Alon-Boppana bound. However, there are still many open problems in this area.

Summary & Key Takeaways

• Pseudorandom graphs have properties of randomness but are deterministically constructed.

• The Alon-Boppana bound states that the second largest eigenvalue in an n, d, lambda graph is at least 2√(d-1), minus a small error term.

• Two different proofs of the Alon-Boppana bound were presented: one using Grothendieck's inequality and one using the trace method.

• The trace method involves counting closed walks in a graph and relates the eigenvalues of a graph to the spectral radius of an infinite d-regular tree.