{"id":"openai-math/Exponential-PSD-rank-of-positively-shifted-matching-matrices","pdf":"https://github.com/openai/math/blob/main/preprints/Exponential-PSD-rank-of-positively-shifted-matching-matrices-October-5-2026/shifted-matching-psd.pdf","url":"https://github.com/openai/math/tree/main/preprints/Exponential-PSD-rank-of-positively-shifted-matching-matrices-October-5-2026","tags":["combinatorics","semidefinite-programming","perfect-matchings"],"score":0,"title":"Exponential PSD rank of positively shifted matching matrices","domain":"Theoretical computer science","family":"126","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"For every fixed $`0\\lt \\rho\\lt 1`$, the matrix indexed by odd vertex sets U and perfect matchings M of K n , with entries $`|M\\cap\\delta(U)|-1+\\rho`$, has real positive semidefinite rank $`2^{\\Omega(n)}`$ as even n tends to infinity. Here $`\\delta(U)`$ is the edge cut of U . Consequently, every exact semidefinite lift of the perfect matching polytope has exponential size.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{},"formalized":false,"family_title":"Exponential semidefinite complexity of perfect matching"}