The Setting
A matching function can be averaged subject to prescribed color-pair counts. The smoothing setting measures its dependence on individual edges through products of edge indicators, and treats the resulting averages as functions of a partition.
The Claim
Definition 1 (Matching tables and polynomial degree). For a nonnegative integer , the vertex set in (1) has vertices, with and Boolean coordinates : (1)✦ A pairing of a finite set is a permutation of satisfying and for every ; write for the set of pairings.✦
For a map from a finite vertex set to a color set , its histogram is the function in (2): (2)✦ For a finite set , a color set , and , the set of fixed-histogram colorings consists of the maps from to with histogram , as in (3): (3)✦ The three-color model uses .
The unordered color-pair type of colors is the index of their unordered pair in the six-element set ordered ; exchanging and leaves this index unchanged.✦ For and , the matching table is the six-entry vector of edge counts in (4): (4)✦
A coloring of , with finite, is identified with the map sending to the ordered pair of colors at and .✦ For a finite set and a reference coloring , the reference table is the six-entry vector of color-pair counts in (5): (5)✦ The matching table relation between and is the constraint in (6): (6)✦
The color-pair count for a finite vertex set , a pairing , a coloring , and an ordered color pair is the number of vertices whose colors at and are and , respectively.✦ For a finite vertex set , a pairing , and a coloring , the cross-color coordinates are the color-pair counts for the distinct pairs , , and , as in (7): (7)✦ For a six-entry table of nonnegative integers, the endpoint color-count vector is the triple in (8); an internal edge contributes two endpoints of its color: (8)✦
The predicate average associated with a condition on a finite set is the linear functional on real functions in (9), with value zero when no element satisfies : (9)✦ For finite sets and and a relation , the incidence matrix is the matrix with entries .✦ The normalized incidence average associated with a relation between finite sets and a real denominator is the linear operator from real functions on to real functions on given by (10), with value zero when : (10)✦ For a relation between finite sets, the fiber averaging operator maps real functions on to real functions on by the normalized incidence average with denominator equal to the cardinality of , as in (11): (11)✦
The edge indicator associated with is the function on in (12): (12)✦ For a family of functions indexed by a set and a nonnegative integer , the space of degree at most is the real span in (13), where the empty product is : (13)✦
The Euclidean matching function space is the real coordinate space indexed by , with inner product .✦ The coordinate identification from to real functions on sends to the matching function .✦ For nonnegative integers , the matching polynomial space is the real span of products of at most edge indicators, including the constant, expressed as vectors through , as specified by (14): (14)✦ The orthogonal polynomial projection is the map on in (15): (15)✦ The low-degree function projection on real matching functions on is the operator obtained from through , as in (16): (16)✦
In the paper, the result reads: for an integer and even , is the uniformly distributed set of perfect matchings on vertices and is the uniformly distributed set of ordered partitions with positive cell sizes summing to ; an admissible table consists of nonnegative integers satisfying , is the average over matchings with table at , is the span of products of at most edge indicators including the constant, and is its orthogonal projection.
What Is Checked
The definitions concern finite vertex sets and fixed-histogram colorings; the projections act on real matching functions for nonnegative integers .
Theorem 1 (Endpoint realization). Let be a finite set, let be a coloring, and let be a six-entry table of nonnegative integers whose endpoint color counts satisfy . There is a pairing with the cross-color counts in (17): (17)✦