§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 and be nonnegative integers, and let be the vertex set of the complete graph .The edge set of consists of the vertex pairs in (1). (1)✦
A perfect matching of is a subset of in which each vertex belongs to exactly one edge, as specified by (2). (2)✦
The positive semidefinite (PSD) cone is the set of real symmetric matrices satisfying the quadratic inequalities in (3). (3)
The Definition
Definition 1. The incidence vector of a perfect matching of is the vector given by (4). (4)✦The perfect matching polytope is the convex hull in (5). (5)✦The polytope has an affine PSD lift of order if there exist an affine subspace and an affine map satisfying (6). (6)✦
In the paper, the result reads: is the convex hull of the perfect-matching incidence vectors in , and a semidefinite lift of of size is a representation of as an affine image of , where is an affine subspace of the real symmetric matrices.
What Is Checked
The definitions are stated for arbitrary nonnegative integers and , using perfect matchings of and affine subspaces and maps over .