The Setting
Let be a finite set, a list of pairs of elements of whose entries are pairwise distinct, and a positive weight on the subsets of , in the role of the paper’s weight . A transversal takes one element from each pair.✦ The chain studied here walks on the transversals and on defect states, in which a pair is left empty and another pair is taken whole, so that the state has type ; it moves by exchanging one element for another, and at a defect state of type it scales the weight by a multiplier . For an observable , a real function on the subsets of , the lemma bounds how far the mean of over the defect states of one type can lie from its mean over the transversals, against the Dirichlet energy of , the quantity with which a Poincaré inequality bounds the variance.
States and Moves
A pair of elements of is empty in a subset of when neither nor lies in ✦, full in when both do✦, and single in when exactly one does.✦
A plain state, or transversal, of is a subset of in which every pair of is single; is the set of transversals.✦ For two distinct pairs and of , a defect state of type is a subset of in which is empty, is full and every other pair of is single; these states form the defect class .✦ A chain state is a subset of that is a plain state or a defect state of some type, and is the set of chain states.✦
Two subsets and of are exchange-adjacent when and for a subset of and distinct elements .✦ The edge set of the chain is the set of ordered pairs of chain states that are exchange adjacent.✦
Slot Totals and Means
A real function on the subsets of is the coefficient function of the multiaffine polynomial in the variables , , and for a vector the derivative is the coefficient function of the directional derivative of that polynomial. The indicator vector of a set has entry on and elsewhere✦, and a pair has direction .✦ The slot total of along a list of pairs is the iterated derivative (1)✦ when the pairs of are disjoint and avoid a set , is the sum of over the sets obtained from by adding one element of each pair.
For two pairs and of and a subset of , the defect total of at is .✦ The masses of the transversals and of a defect class are (2) and, with the pointwise product , the means of over them are (3)
For an element of a pair of and an element of another pair of , the transversal event is the set of transversals that contain and . Its mass and the mean of over it are (4)
The Slot Signature
The face Hessian of at a subset of is the symmetric matrix with rows and columns indexed by , zero diagonal, and entry at distinct and .✦
A bilinear form on a real vector space has one positive direction when, for every with , every with satisfies ; for a symmetric form this is the condition of at most one positive eigenvalue.✦
A real function on the subsets of has the slot signature property when, for every list of pairs of elements of and every subset of , the bilinear form of the face Hessian has one positive direction.✦
Multipliers and Energy
A family of multipliers for is a family of positive reals , one for each ordered pair of pairs of . The multipliers are good when (5) and the left inequality is the lower half of (5). The multiplier of a subset of is when is a defect state of type , and otherwise.✦ The conductance of an edge is (6)✦
For subsets and of , a subset of respects when it contains and is disjoint from ✦, and an edge respects when both of its endpoints do.✦ Over a finite set of edges with conductances , the energy of a function on the subsets of restricted to is half the sum of over the edges that respect .✦ The Dirichlet energy of a function on the subsets of for the chain is the energy of over the edge set with conductances , restricted to : (7)
The Claim
Theorem 1. Let be a list of pairs of elements of a finite set whose entries are pairwise distinct, and let and be two distinct pairs of . Let be a positive weight on the subsets of with the slot signature property, let be positive multipliers that satisfy the lower half of (5), and let be a real function on the subsets of . Then there is a constant , depending on alone, such that for every element of and every element of (8)✦ and the mean of over the defect class of type satisfies (9)✦
In the paper, the result reads: for good multipliers, every function on and every defect type , the paper’s type , there is an event prescribing the selected elements of and with such that with and , where and is the paper’s probability measure on .
What Is Checked
Both bounds are stated over a finite set with a list of pairs whose entries are pairwise distinct, two distinct pairs and of , a positive weight with the slot signature property, positive multipliers satisfying the lower half of (5), and an arbitrary real function on the subsets of , with the Dirichlet energy (7) of the chain on plain and defect states with exchange edges and conductances (6). The bound (8) is stated in addition over a choice of one element of and one element of , which fixes the transversal event .