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 a new geometric graph parameter $\egd(G)$, defined as the smallestinteger $r\ge 1$ for which any partial symmetric matrix which is completable toa correlation matrix and whose entries are specified at the positions of theedges of $G$, can be completed to a matrix in the convex hull of correlationmatrices of $\rank $ at most $r$. This graph parameter is motivated by itsrelevance to the problem of finding low rank solutions to semidefinite programsover the elliptope, and also by its relevance to the bounded rank Grothendieckconstant. Indeed, $\egd(G)\le r$ if and only if the rank-$r$ Grothendieckconstant of $G$ is equal to 1. We show that the parameter $\egd(G)$ is minormonotone, we identify several classes of forbidden minors for $\egd(G)\le r$and we give the full characterization for the case $r=2$. We also show an upperbound for $\egd(G)$ in terms of a new tree-width-like parameter $\sla(G)$,defined as the smallest $r$ for which $G$ is a minor of the strong product of atree and $K_r$. We show that, for any 2-connected graph $G\ne K_{3,3}$ on atleast 6 nodes, $\egd(G)\le 2$ if and only if $\sla(G)\le 2$.

Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope