Tales of Hoffman: from a distance
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914201770917888 |
|---|---|
| author | Abiad, Aida Meeus, Jan |
| author_facet | Abiad, Aida Meeus, Jan |
| contents | Hoffman proved that a graph $G$ with adjacency eigenvalues $λ_1\geq \cdots \geq λ_n$ and chromatic number $χ(G)$ satisfies $χ(G)\geq 1+κ,$ where $κ$ is the smallest integer such that $$λ_1+\sum_{i=1}^κλ_{n+1-i}\leq 0.$$ We extend this eigenvalue bound to the distance-$k$ setting, and also show a strengthening of it by proving that it also lower bounds the corresponding quantum distance coloring graph parameter. The new bound depends on a degree-$k$ polynomial which can be chosen freely, so one needs to make a good choice of the polynomial to obtain as strong a bound as possible. We thus propose linear programming methods to optimize it. We also investigate the implications of the new bound for the quantum distance chromatic number, showing that it is sharp for some classes of graphs. Finally, we extend the Hoffman bound to the distance setting of the vector chromatic number. Our results extend and unify several previous bounds in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_13187 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tales of Hoffman: from a distance Abiad, Aida Meeus, Jan Combinatorics Quantum Physics Hoffman proved that a graph $G$ with adjacency eigenvalues $λ_1\geq \cdots \geq λ_n$ and chromatic number $χ(G)$ satisfies $χ(G)\geq 1+κ,$ where $κ$ is the smallest integer such that $$λ_1+\sum_{i=1}^κλ_{n+1-i}\leq 0.$$ We extend this eigenvalue bound to the distance-$k$ setting, and also show a strengthening of it by proving that it also lower bounds the corresponding quantum distance coloring graph parameter. The new bound depends on a degree-$k$ polynomial which can be chosen freely, so one needs to make a good choice of the polynomial to obtain as strong a bound as possible. We thus propose linear programming methods to optimize it. We also investigate the implications of the new bound for the quantum distance chromatic number, showing that it is sharp for some classes of graphs. Finally, we extend the Hoffman bound to the distance setting of the vector chromatic number. Our results extend and unify several previous bounds in the literature. |
| title | Tales of Hoffman: from a distance |
| topic | Combinatorics Quantum Physics |
| url | https://arxiv.org/abs/2512.13187 |