OctoInformBeta

OpenAI preprint, October 2026 · §1. Introduction

§1 (setting): the perfect matching polytope and exact affine lifts: Exact semidefinite lifts are measured by their matrix order

Matching incidence vectors determine the polytope.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The question is which matrix orders admit an exact semidefinite representation of the perfect matching polytope. Let nn and rr be nonnegative integers, and let Vn={0,…,n−1}V_n=\{0,\ldots,n-1\} be the vertex set of the complete graph KnK_n. The edge set EnE_n of KnK_n consists of the vertex pairs in (1). En={(i,j)∈Vn×Vn:i<j}.E_n=\{(i,j)\in V_n\times V_n:i<j\}.(1)✦

A perfect matching MM of KnK_n is a subset of EnE_n in which each vertex belongs to exactly one edge, as specified by (2). |{(i,j)∈M:i=vorj=v}|=1for every v∈Vn.\bigl|\{(i,j)\in M:i=v\ \text{or}\ j=v\}\bigr|=1 \qquad\text{for every }v\in V_n.(2)✦

The positive semidefinite (PSD) cone 𝕊+r\mathbb S_+^r is the set of real symmetric r×rr\times r matrices satisfying the quadratic inequalities in (3). 𝕊+r={X∈ℝr×r:X=X𝖳,v𝖳Xv≥0 for every v∈ℝr}.\mathbb S_+^r =\{X\in\mathbb R^{r\times r}:X=X^{\mathsf T},\quad v^{\mathsf T}Xv\geq0\text{ for every }v\in\mathbb R^r\}.(3)

The Definition

Definition 1. The incidence vector xM∈ℝEnx_M\in\mathbb R^{E_n} of a perfect matching MM of KnK_n is the vector given by (4). xM(e)={1,e∈M,0,e∉M,e∈En.x_M(e)= \begin{cases} 1,&e\in M,\\ 0,&e\notin M, \end{cases} \qquad e\in E_n.(4)✦ The perfect matching polytope Pn⊆ℝEnP_n\subseteq\mathbb R^{E_n} is the convex hull in (5). Pn=conv⁡{xM:M is a perfect matching of Kn}.P_n=\operatorname{conv}\{x_M:M\text{ is a perfect matching of }K_n\}.(5)✦ The polytope PnP_n has an affine PSD lift of order rr if there exist an affine subspace L⊆ℝr×rL\subseteq\mathbb R^{r\times r} and an affine map T:ℝr×r→ℝEnT:\mathbb R^{r\times r}\to\mathbb R^{E_n} satisfying (6). T(L∩𝕊+r)=Pn.T(L\cap\mathbb S_+^r)=P_n.(6)✦

In the paper, the result reads: PnP_n is the convex hull of the perfect-matching incidence vectors in ℝEn\mathbb R^{E_n}, and a semidefinite lift of PnP_n of size rr is a representation of PnP_n as an affine image of L∩𝕊+rL\cap\mathbb S_+^r, where LL is an affine subspace of the real symmetric r×rr\times r matrices.

What Is Checked

The definitions are stated for arbitrary nonnegative integers nn and rr, using perfect matchings of KnK_n and affine subspaces and maps over ℝ\mathbb R.