The Setting
Take a finite set , a list of disjoint pairs of its elements, and a positive weight on the subsets of ; the two matroids whose common bases are counted enter only through a condition on , the slot signature property. A transversal of is a set made of one element from each pair, and is the distribution on transversals proportional to . A Markov chain moves by exchanging one element for another among the sets that meet every pair once and the defect sets, weighted by times a multiplier . The question is the chain’s Poincaré constant seen from the transversals: how large the variance of a function under can be against the chain’s Dirichlet form .
Slot Totals and Slot Variance
A list of pairs of elements of is fresh for a set when its entries are pairwise distinct and none lies in .✦ For a pair and a list , is the list that starts with and continues with , and is the length of .
A multiaffine polynomial in variables , , is given by its coefficient function on the subsets of , as , where is the product of the with . The slot total of along is the coefficient function of the iterated directional derivative of this polynomial along the indicator vectors of the pairs of .✦ When is fresh for a set , (1) Set and .
For a function on the subsets of , the slot variance of along at is the number (2)✦ When is fresh for , is times the variance of under the distribution proportional to on the sets summed in (1), so that .
For two pairs and , the defect total of along at is the slot total of along with and removed, taken at with both elements of added.✦ Set .
The face Hessian of at is the symmetric matrix with rows and columns indexed by , zero diagonal, and entry for distinct and .✦ A bilinear form on a real vector space has one positive direction when, for every with , every with has ; for a symmetric form this is having at most one positive eigenvalue.✦ A function on the subsets of has the slot signature property when, for every list of pairs and every , the face Hessian has one positive direction.✦
The Chain
A pair is empty, full or single in a set when contains none, both or exactly one of its elements. A plain state of is a subset of in which every pair of is single.✦ For two distinct pairs and of , a defect state of for and is a subset of in which is empty, is full and every other pair of is single.✦ A chain state of is a plain state or a defect state for some two pairs.✦ Two subsets and of are exchange-adjacent when and for a set and distinct elements and outside , and the chain’s edge set consists of the ordered pairs of exchange-adjacent chain states of .
The multipliers are positive reals , one for every two pairs and . The multiplier of a set is when is a defect state of for and , and otherwise✦, and the conductance of an edge is (3)✦ The multipliers are good when for any two distinct pairs and of ; the lower half is the left inequality.
For subsets and of , a subset of respects when it contains and avoids ; an edge respects when both and respect . For a finite set of ordered pairs of subsets of with weights , the energy of on restricted to is (4)✦ and is the chain’s Dirichlet form.
A variance node of is a triple of a list of pairs of and two disjoint subsets and of such that is fresh for and every pair of outside has one element in and the other in .✦
The Claim
Theorem 1 (Sink of scores). Let be a finite nonempty set, and let real scores , for , satisfy the pair inequality for distinct and and the triple inequality for pairwise distinct , and . Then the scores have a sink, an index with (5)✦
Theorem 2 (Sink for slot totals). Let be a positive function on the subsets of with the slot signature property, let be a nonempty list of pairs and a list that contains every pair of , and let and be subsets of such that is fresh for and is fresh for . Then there is a pair of such that every pair of satisfies (6)✦
Theorem 3 (Adaptive splitting). Let and be functions on the subsets of with positive, let be a finite set of ordered pairs of subsets of with weights on , let , and let be a family of triples of a list of pairs and two subsets of . Suppose that every triple in with nonempty splits: there are a pair and a list such that is a reordering of , is fresh for , the triples and are in , and (7) Then every triple in satisfies (8)✦
Theorem 4 (Variance on transversals). Let be a list of pairs of elements of , fresh for , let be a positive function on the subsets of with the slot signature property, let positive multipliers satisfy the lower half for any two distinct pairs and of , and let be a function on the subsets of . Then (9)✦ Moreover, for every variance node of with nonempty there are a pair and a list such that is a reordering of , is fresh for , the triples and are variance nodes of , and (10)✦
In the paper, the result reads: for good multipliers and every real function on the chain’s state space , with .
What Is Checked
The bound (9) is stated over the slot totals, defect totals and slot variance of a positive with the slot signature property along a list of pairs fresh for , and over the Dirichlet form of the chain that joins the plain and defect states of by exchange edges with conductance (3), for multipliers satisfying the lower half; the one-step bound (10) is stated over the variance nodes of and the energy (4) restricted to the edges that respect .