Conic programming to understand sums of squares of eigenvalues 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_ | 1866910695887470592 |
|---|---|
| author | Coutinho, Gabriel Spier, Thomás Jung Zhang, Shengtong |
| author_facet | Coutinho, Gabriel Spier, Thomás Jung Zhang, Shengtong |
| contents | In this paper we prove a conjecture by Wocjan, Elphick and Anekstein (2018) which upper bounds the sum of the squares of the positive (or negative) eigenvalues of the adjacency matrix of a graph by an expression that behaves monotonically in terms of the vector chromatic number. One of our lemmas is a strengthening of the Cauchy-Schwarz inequality for Hermitian matrices when one of the matrices is positive semidefinite.
A related conjecture due to Bollobás and Nikiforov (2007) replaces the vector chromatic number by the clique number and sums over the first two eigenvalues only. We prove a version of this conjecture with weaker constants. An important consequence of our work is a proof that for any fixed $r$, computing a rank $r$ optimum solution to the vector chromatic number semidefinite programming is NP-hard.
We also present a vertex weighted version of some of our results, and we show how it leads quite naturally to the known vertex-weighted version of the Motzkin-Straus quadratic optimization formulation for the clique number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08184 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Conic programming to understand sums of squares of eigenvalues of graphs Coutinho, Gabriel Spier, Thomás Jung Zhang, Shengtong Combinatorics Optimization and Control Spectral Theory In this paper we prove a conjecture by Wocjan, Elphick and Anekstein (2018) which upper bounds the sum of the squares of the positive (or negative) eigenvalues of the adjacency matrix of a graph by an expression that behaves monotonically in terms of the vector chromatic number. One of our lemmas is a strengthening of the Cauchy-Schwarz inequality for Hermitian matrices when one of the matrices is positive semidefinite. A related conjecture due to Bollobás and Nikiforov (2007) replaces the vector chromatic number by the clique number and sums over the first two eigenvalues only. We prove a version of this conjecture with weaker constants. An important consequence of our work is a proof that for any fixed $r$, computing a rank $r$ optimum solution to the vector chromatic number semidefinite programming is NP-hard. We also present a vertex weighted version of some of our results, and we show how it leads quite naturally to the known vertex-weighted version of the Motzkin-Straus quadratic optimization formulation for the clique number. |
| title | Conic programming to understand sums of squares of eigenvalues of graphs |
| topic | Combinatorics Optimization and Control Spectral Theory |
| url | https://arxiv.org/abs/2411.08184 |