English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the lift-and-project rank of the stable set polytopes of graphs withrespect to the Lov{\'a}sz--Schrijver SDP operator $\LS_+$, with a particularfocus on a search for relatively small graphs with high $\LS_+$-rank (the leastnumber of iterations of the $\LS_+$ operator on the fractional stable setpolytope to compute the stable set polytope). We provide families of graphswhose $\LS_+$-rank is asymptotically a linear function of its number ofvertices, which is the best possible up to improvements in the constant factor(previous best result in this direction, from 1999, yielded graphs whose$\LS_+$-rank only grew with the square root of the number of vertices).

Stable Set Polytopes with High Lift-and-Project Ranks for the Lov\'asz-Schrijver SDP Operator