Closure correlations in paving and low-corank matroids
Loading original first page…
Abstract
Sample an independent set after deleting two marked elements of a finite matroid, with probability proportional to the product of its element weights. We prove that the two events that the sampled set spans the marked elements are positively correlated for every paving matroid and for every matroid of corank at most three. In both cases the covariance numerator has nonnegative coefficients in the individual weights. The paving result follows from a monomial-preserving circuit exchange and extends to a condition on circuits through just one mark. The low-corank result uses complementary spanning sets in the dual and a coefficient inequality for two pencils of lines. Exact minor and series and parallel extension identities give further closure properties, and the proofs yield strictness criteria for positive weights. We also give a portable integer certificate for the binary rank-four consequence of earlier reported computations, including its forest-connectivity specialization.
Read the full paper in the original PDF.