A connection between the $A_α$-spectrum and the Lovász theta number
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915252660076544 |
|---|---|
| author | Coutinho, Gabriel Oliveira, Thiago |
| author_facet | Coutinho, Gabriel Oliveira, Thiago |
| contents | We show that the smallest $α$ so that $αD + (1-α)A \succcurlyeq 0$ is at least $1/\vartheta(\overline{G})$, significantly improving upon a result due to Nikiforov and Rojo (2017). In fact, we display an even stronger connection: if the nonzero entries of $A$ are allowed to vary and those of $D$ vary accordingly, then we show that this smallest $α$ is in fact equal to $1/\vartheta(\overline{G})$. We also show other results obtained as an application of this optimization framework, including a connection to the well-known quadratic formulation for $ω(G)$ due to Motzkin and Straus (1964). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_14884 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A connection between the $A_α$-spectrum and the Lovász theta number Coutinho, Gabriel Oliveira, Thiago Combinatorics We show that the smallest $α$ so that $αD + (1-α)A \succcurlyeq 0$ is at least $1/\vartheta(\overline{G})$, significantly improving upon a result due to Nikiforov and Rojo (2017). In fact, we display an even stronger connection: if the nonzero entries of $A$ are allowed to vary and those of $D$ vary accordingly, then we show that this smallest $α$ is in fact equal to $1/\vartheta(\overline{G})$. We also show other results obtained as an application of this optimization framework, including a connection to the well-known quadratic formulation for $ω(G)$ due to Motzkin and Straus (1964). |
| title | A connection between the $A_α$-spectrum and the Lovász theta number |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2311.14884 |