Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911667897499648 |
|---|---|
| author | Au, Yu Hin Tunçel, Levent |
| author_facet | Au, Yu Hin Tunçel, Levent |
| contents | We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász--Schrijver SDP operator $\text{LS}_+$ applied to the fractional stable set polytope. In particular, we show that for every positive integer $\ell$, the smallest possible graph with $\text{LS}_+$-rank $\ell$ contains $3\ell$ vertices. This result is sharp and settles a conjecture posed by Lipták and the second author in 2003, as well as answers a generalization of a problem posed by Knuth in 1994. We also show that for every positive integer $\ell$ there exists a vertex-transitive graph on at most $4\ell+12$ vertices with $\text{LS}_+$-rank at least $\ell$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07413 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator Au, Yu Hin Tunçel, Levent Combinatorics Computational Complexity Discrete Mathematics Optimization and Control 90C22, 90C27 We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász--Schrijver SDP operator $\text{LS}_+$ applied to the fractional stable set polytope. In particular, we show that for every positive integer $\ell$, the smallest possible graph with $\text{LS}_+$-rank $\ell$ contains $3\ell$ vertices. This result is sharp and settles a conjecture posed by Lipták and the second author in 2003, as well as answers a generalization of a problem posed by Knuth in 1994. We also show that for every positive integer $\ell$ there exists a vertex-transitive graph on at most $4\ell+12$ vertices with $\text{LS}_+$-rank at least $\ell$. |
| title | Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator |
| topic | Combinatorics Computational Complexity Discrete Mathematics Optimization and Control 90C22, 90C27 |
| url | https://arxiv.org/abs/2501.07413 |