Maximum spectral gaps of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912636847783936 |
|---|---|
| author | Brooks, George Linz, William Lu, Linyuan |
| author_facet | Brooks, George Linz, William Lu, Linyuan |
| contents | The spread of a graph $G$ is the difference $λ_1 - λ_n$ between the largest and smallest eigenvalues of its adjacency matrix. Breen, Riasanovsky, Tait and Urschel recently determined the graph on $n$ vertices with maximum spread for sufficiently large $n$. In this paper, we study a related question of maximizing the difference $λ_{i+1} - λ_{n-j}$ for a given pair $(i, j)$ over all graphs on $n$ vertices. We give upper bounds for all pairs $(i, j)$, exhibit an infinite family of pairs where the bound is tight, and show that for the pair $(1, 0)$ the extremal example is unique. These results contribute to a line of inquiry pioneered by Nikiforov aiming to maximize different linear combinations of eigenvalues over all graphs on $n$ vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15476 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maximum spectral gaps of graphs Brooks, George Linz, William Lu, Linyuan Combinatorics The spread of a graph $G$ is the difference $λ_1 - λ_n$ between the largest and smallest eigenvalues of its adjacency matrix. Breen, Riasanovsky, Tait and Urschel recently determined the graph on $n$ vertices with maximum spread for sufficiently large $n$. In this paper, we study a related question of maximizing the difference $λ_{i+1} - λ_{n-j}$ for a given pair $(i, j)$ over all graphs on $n$ vertices. We give upper bounds for all pairs $(i, j)$, exhibit an infinite family of pairs where the bound is tight, and show that for the pair $(1, 0)$ the extremal example is unique. These results contribute to a line of inquiry pioneered by Nikiforov aiming to maximize different linear combinations of eigenvalues over all graphs on $n$ vertices. |
| title | Maximum spectral gaps of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.15476 |