Semidefinite programming bounds on fractional cut-cover and maximum 2-SAT for highly regular graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914560147980288 |
|---|---|
| author | Assumpção, Henrique Coutinho, Gabriel |
| author_facet | Assumpção, Henrique Coutinho, Gabriel |
| contents | We use semidefinite programming to bound the fractional cut-cover parameter of graphs in association schemes in terms of their smallest eigenvalue. We also extend the equality cases of a primal-dual inequality involving the Goemans-Williamson semidefinite program, which approximates MAXCUT, to graphs in certain coherent configurations. Moreover, we obtain spectral bounds for MAX 2-SAT when the underlying graphs belong to a symmetric association scheme by means of a certain semidefinite program used to approximate quadratic programs, and we further develop this technique in order to explicitly compute the optimum value of its gauge dual in the case of distance-regular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10548 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Semidefinite programming bounds on fractional cut-cover and maximum 2-SAT for highly regular graphs Assumpção, Henrique Coutinho, Gabriel Optimization and Control Combinatorics 05E30 (Primary), 90C22 (Secondary) We use semidefinite programming to bound the fractional cut-cover parameter of graphs in association schemes in terms of their smallest eigenvalue. We also extend the equality cases of a primal-dual inequality involving the Goemans-Williamson semidefinite program, which approximates MAXCUT, to graphs in certain coherent configurations. Moreover, we obtain spectral bounds for MAX 2-SAT when the underlying graphs belong to a symmetric association scheme by means of a certain semidefinite program used to approximate quadratic programs, and we further develop this technique in order to explicitly compute the optimum value of its gauge dual in the case of distance-regular graphs. |
| title | Semidefinite programming bounds on fractional cut-cover and maximum 2-SAT for highly regular graphs |
| topic | Optimization and Control Combinatorics 05E30 (Primary), 90C22 (Secondary) |
| url | https://arxiv.org/abs/2505.10548 |