Ratio bound (Lovász number) versus inertia bound
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913833031827456 |
|---|---|
| author | Ihringer, Ferdinand |
| author_facet | Ihringer, Ferdinand |
| contents | Matthew Kwan and Yuval Wigderson showed that for an infinite family of graphs, the Lovász number gives an upper bound of $O(n^{3/4})$ for the size of an independent set (where $n$ is the number of vertices), while the weighted inertia bound cannot do better than $Ω(n)$. Here we point out that there is an infinite family of graphs for which the Lovász number is $Ω(n^{3/4})$, while the unweighted inertia bound is $O(n^{1/2})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_09524 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Ratio bound (Lovász number) versus inertia bound Ihringer, Ferdinand Combinatorics Matthew Kwan and Yuval Wigderson showed that for an infinite family of graphs, the Lovász number gives an upper bound of $O(n^{3/4})$ for the size of an independent set (where $n$ is the number of vertices), while the weighted inertia bound cannot do better than $Ω(n)$. Here we point out that there is an infinite family of graphs for which the Lovász number is $Ω(n^{3/4})$, while the unweighted inertia bound is $O(n^{1/2})$. |
| title | Ratio bound (Lovász number) versus inertia bound |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2312.09524 |