Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.09524 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |