The Setting
A real positive semidefinite (PSD) trace factorization of matching cut data assigns PSD matrices to cuts and perfect matchings, with each entry equal to the trace of the corresponding matrix product. Here the cuts are indexed by Boolean strings, and the matching vertices consist of two fixed parts and a family of blocks indexed by the bit positions.
Write . For nonnegative integers , let and be disjoint copies of . The global vertex set is (1)✦
A perfect matching on a set is a permutation of satisfying and for every ; denote the set of these matchings by .✦
For a set , a perfect matching on , and a permutation of , the relabelling of by is the perfect matching given by (2)✦
For sets and a Boolean string , the global cut coloring is one on , zero on , and equal to on each vertex of .✦ On this is the map given by (3)✦
For a perfect matching on a finite set , a color set , a coloring , and a color pair , the table coordinate is the number of matching endpoints with the specified ordered colors: (4)✦ Thus the factorization entries considered here are cut values from (4), with the cuts of (3) and matchings on (1).
The interpolation grid for a nonnegative integer is the set of triples of integers with coordinates between and .✦ For a nonnegative integer , the sample index set is the disjoint union of the five-element set and the interpolation grid : (5)✦
The Claim
Definition 1. For nonnegative integers , the block size is the nonnegative integer given by (6)✦ The vertex size associated with the block size in (6) is the positive integer given by (7)✦
Theorem 1. Let be a finite set and a nonnegative integer. For each Boolean string , let be a real PSD matrix indexed by with trace one. Let be real matrices indexed by such that and for every and , where is the identity matrix indexed by . Suppose , , and for every . Then the nearly perfect bit tests satisfy (8)✦
Theorem 2. For every nonnegative integer , there exist nonnegative integers with and a real number with the following property. Take positive integers satisfying and , and a real number . Let , indexed by permutations of and strings , and , indexed by , be real PSD matrices of order . Suppose their trace bounds and factorization identities are (9) where relabelling is as in (2). Suppose also that the sample set in (5) satisfies the numerical conditions (10) Under (9) and (10), the conditional cell lower bound is (11)✦
In the paper, the result reads: local restriction channels, Fourier smoothing, and an expanding parity system exclude factorization size at most with proportional to the number of vertices.
What Is Checked
The conditional bound (11) is stated over real PSD matrix families on the matchings and relabelled Boolean cuts of ; the bit test bound (8) is stated over density matrices and paired effects on an arbitrary finite index set .