Algebraic, geometric, and spectral properties of regular graphs
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
In Chapter 1 we cover the notation and basic definitions used throughout this dissertation. We provide definitions, examples, and basic results for distance-regular graphs since the results of this dissertation are related to these graphs. We cover definitions and results for expanders, Cayley graphs, and embedding graphs into Euclidean spaces. ☐ In Chapter 2 we study embedding of distance-regular graphs into Euclidean spaces with least distortion. Embedding graphs into Euclidean spaces is a topic well-studied in mathematics and computer science. In 2008, Vallentin studied this problem for distance-regular graphs and obtained a lower bound for the least distortion of a distance-regular graph. In addition, he showed that this bound is tight for the Hamming and the Johnson graphs as well as strongly regular graphs and conjectured that his bound is tight for all distance-regular graphs. In Chapter 2, we provide several counterexamples to this conjecture with diameter 4 and larger. We suggest three alternative conjectures and prove them for various families of distance-regular graphs and for distance-regular graphs of diameter 3. ☐ In Chapter 3 we study eigenvalues of Grassmann graphs, bilinear forms graphs, and Hermitian forms graphs. In 2018, Brouwer, Cioaba, Ihringer and McGinnis obtained some new results involving the eigenvalues of various distance-regular graphs of classical parameters. They posed some conjectures related to the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs. In Chapter 3, we prove some of their conjectures by using estimates of Gaussian coefficients. ☐ Let q be a prime power. The family of graphs D(k,q), defined for any positive integer k and prime power q, were introduced by Lazebnik and Ustimenko in 1995. To this day, the connected components of the graphs D(k,q), provide the best known general lower bound for the size of a graph of given order and given girth. Furthermore, Ustimenko conjectured that the second largest eigenvalue of D(k,q) is always less than or equal to 2√q. If true, this would imply that for a fixed q and k growing, D(k,q) would define a family of expanders that are nearly Ramanujan. In Chapter 4 we prove the smallest open case of the conjecture, showing that for all odd prime powers q, the second largest eigenvalue of D(5,q) is lessthan or equal to 2√q. We use tools from the representation theory of finite groups, and the characters of finite fields.
Description
Keywords
Cayley graphs, Distance-regular graphs, Euclidean embedding, Expanders, Smallest eigenvalues, Spectral graph theory