The Setting
Prescribing the numbers of matching edges within and between the cells of a partition of the vertices defines a conditional average of a function on perfect matchings. Uniform smoothing concerns the contribution from functions orthogonal to products of a bounded number of edge indicators.
Put and , with the colors indexed in this order. For an integer , the paired vertex set and its size are (1)โฆ A matching involution on a finite set is a permutation satisfying and for every ; write for the set of these involutions and use on the vertex set in (1).โฆ The Euclidean matching function space has inner product .โฆ The uniform norm of a real function on a nonempty finite set is the norm given by (2); denotes the induced operator norm. (2)
The histogram of a coloring is the vector of its cell sizes.โฆ The colorings with prescribed histogram form the set (3) The unordered color pair type of colors is the label with the smaller color written first.โฆ Its six types are ordered ; the distinct color pairs are , in that order. The matching color table of a matching and a coloring is the table of unoriented edge counts, with diagonal endpoint counts twice the internal-edge counts: (4)โฆ
For any finite set , the paired vertex coloring correspondence sends a coloring to the ordered-pair coloring .โฆ The reference color table counts these pairs by their unordered types: (5)โฆ
The edge incidence coordinate for vertices is the real function on that indicates whether the matching pairs with .โฆ For a nonnegative integer and a family of real functions on a common set , the degree-bounded span is the linear span of products of at most members, including the empty product .โฆ The matching polynomial space on a finite vertex set is the real linear span of products of at most edge incidence coordinates, including the empty product : (6) The orthogonal polynomial projection is the orthogonal projection onto the subspace in (6).โฆ
The incidence matrix of a relation between finite sets and has entry when holds and otherwise.โฆ The normalized incidence average of a relation between finite sets and , with real normalizing factor , is the operator from real functions on to real functions on given by (7)โฆ The fiber average of a relation between finite sets and is the operator from real functions on to real functions on that uses each fiber cardinality as the normalizing factor in (7)โฆ; the uniform average over a subset is the uniform averaging functional on real functions on : (8) A zero denominator gives value zero in (7) and (8).
A table of six nonnegative integer counts is admissible for a coloring when the matching fiber below is nonempty. The conditional table operator associated with a table of six nonnegative integer counts sends a real function on to its uniform average over the matching fiber at each coloring : (9) For a reference coloring , reference table compatibility is the relation between and from (3).โฆ Its fiber average is in (9), with the reference table from (5) and matching tables from (4).
The Claim
Theorem 1 (Uniform smoothing and polynomial table averages). Fix an integer . There are integers and with the following property. Let , let be a reference coloring with for each , and let . Then (10)โฆ Let be a finite set, let be an integer, let be a coloring, and let . There is a polynomial of total degree at most satisfying (11) for every table admissible for . (11)โฆ
In the paper, with denoting the identity operator, the result reads: for every fixed number of cells and real there are integers and such that, for every even , every positive integer cell-size vector summing to , and every admissible table , the uniform operator norm satisfies , and, for each fixed partition and function , all values over admissible tables are represented by one polynomial of total degree at most in the intercell counts.
What Is Checked
The smoothing estimate (10) is stated over Euclidean matching functions and reference table fibers with three positive cell sizes, while the polynomial representation (11) is stated over edge-product spans on for arbitrary finite .