Publication
STOC 1992
Conference paper

Balanced matroids

Download paper

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.

Date

Publication

STOC 1992

Authors

Resources

Share