Series:

Memoirs of the American Mathematical Society

2 total works

Cover of Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture
In this paper the author establishes some foundations regarding sheaves of vector spaces on graphs and their invariants, such as homology groups and their limits. He then uses these ideas to prove the Hanna Neumann Conjecture of the 1950s; in fact, he proves a strengthened form of the conjecture.

Cover of A Proof of Alon's Second Eigenvalue Conjecture and Related Problems
A $d$-regular graph has largest or first (adjacency matrix) eigenvalue $\lambda 1=d$. Consider for an even $d\ge 4$, a random $d$-regular graph model formed from $d/2$ uniform, independent permutations on $\{1,\ldots,n\}$. The author shows that for any $\epsilon>0$ all eigenvalues aside from $\lambda 1=d$ are bounded by $2\sqrt{d-1}\;+\epsilon$ with probability $1-O(n{-\tau})$, where $\tau=\lceil \bigl(\sqrt{d-1}\;+1\bigr)/2 \rceil-1$. He also shows that this probability is at most $1-c/n{\tau'}$, for a constant $c$ and a $\tau'$ that is either $\tau$ or $\tau+1$ (""more often"" $\tau$ than $\tau+1$). He proves related theorems for other models of random graphs, including models with $d$ odd.