The Setting
Approximate counting of the common bases of two matroids and runs through a multiaffine polynomial with positive coefficients whose variables come in disjoint pairs. Lemma 3.2 is a pair of quadratic inequalities between two kinds of sums of its coefficients, slot totals and defect totals.
The library states the lemma for an arbitrary positive function on the subsets of a finite set and a list of disjoint pairs of ; the matroids enter only through the hypothesis that has the slot signature property. It also states two inequalities for symmetric bilinear forms with one positive direction, the first a reverse Cauchy-Schwarz inequality.
Slot Totals and Defect Totals
A multiaffine polynomial on a finite set is a polynomial in variables , , of degree at most one in each variable, (1) given by its coefficient function on the subsets of . The directional derivative of along a real vector is , and the iterated derivative of along a list of vectors is .✦
The indicator vector of a finite set has entry at the elements of and elsewhere.✦ A pair is an ordered pair of elements of ; its direction is , and stands for .✦ A list of pairs is fresh for a set when the entries of its pairs are pairwise distinct and none of them lies in .✦
The slot total of along a list of pairs is the iterated derivative of along the directions of the pairs of : (2)✦ When is fresh for , the coefficient of at is (3) the sum running over the sets made of one entry of each pair of .
For two pairs and , the defect total of along at is the slot total along the list with and removed, at the set : (4)✦ When is fresh for and lie in , it is the sum of over the sets that add to both entries of , no entry of and one entry of each other pair of .
One Positive Direction
A bilinear form on a real vector space has one positive direction if, whenever has , every with has .✦ For a symmetric form this is the condition of at most one positive eigenvalue.
The face Hessian of a multiaffine polynomial at a set is the symmetric matrix indexed by , with zero diagonal and (5)✦ it is the Hessian at the origin of the derivative of in the variables of , restricted to the other variables.
A multiaffine polynomial on has the slot signature property if, for every list of pairs of elements of and every set , the bilinear form of the face Hessian of the slot total at has one positive direction.✦
The Claim
Theorem 1. Let be a multiaffine polynomial on with positive coefficients and the slot signature property, let , and let be a list of pairs fresh for , with slot total and defect totals along at . For distinct pairs and of , (6)✦ and for pairwise distinct pairs , , of , (7)✦ In terms of slot totals alone, for pairs , , and a list of pairs, with the list that starts with and and goes on with : if is fresh for , then (8)✦ and if is fresh for , then (9)✦ Let be a symmetric bilinear form on a real vector space with one positive direction. For with , (10)✦ and for with , , , and , (11)✦
In the paper, the result reads: for a partial transversal assignment and distinct unassigned indices , , , and , where is the slot total and the defect total of the th pair and the th pair .
What Is Checked
The claim is stated over a multiaffine polynomial on a finite set with positive coefficients and the slot signature property, a set , a list of pairs fresh for with its slot totals and defect totals, and, in (10) and (11), a symmetric bilinear form with one positive direction on a real vector space.