Balanced matroids

Abstract

We introduce the notion of "balance", and say that a ma-troid is balanced if the matroid and all its minors satisfy the property that, for a randomly chosen basis, the presence of an element can only make any other element less likely. We establish strong expansion properties for the bases-exchange graph of balanced matroids; consequently, the set of bases of a balanced matroid can be sampled and approximately counted using rapidly mixing Markov chains. Specific classes for which balance is known to hold include graphic and regular matroids.