×

zbMATH — the first resource for mathematics

Rapid mixing of some linear matroids and other combinatorial objects. (English) Zbl 0954.05015
Introduction: We address the problem of calculating the number of bases of a matroid given by, say, the independence oracle. Motivated by A. Sinclair [Algorithms for random generation and counting: a Markov chain approach (Boston, MA: Birkhäuser) (1993; Zbl 0780.68096)] and others, one approach to this problem has been the construction of a Markov chain based on the base adjacency graph of the matroid and to try and show that this chain mixes rapidly, i.e., \(1- \lambda_2\geq{1\over p(n)}\), where \(n\) is the size of the ground set. A major open problem in this area is whether the base-adjacency graphs for matroids mix rapidly at all.
In this paper, we show that the base-adjacency graphs of a large class of linear matroids mix rapidly. This class was studied by J. Oxley, K. Prendergast and D. Row [J. Aust. Math. Soc., Ser. A 32, 380-387 (1982; Zbl 0485.05023)], as transversal matroids of a nested sequence of sets. We call this class as Schubert matroids since they are related to the well-known and studied Schubert varieties in algebraic geometry. We prove rapid-mixing by showing that this class obeys a weaker variation of balance. Previous to this, matroids known to enjoy rapid-mixing properties were graphic matroids and some subfamilies of binary matroids (see M. Dyer and A. Frieze [Math. Program. 64A, No. 1, 1-16 (1994; Zbl 0820.90066)]). We have thus exhibited another large class of matroids which show a variation of balance and therefore mix rapidly. Balance in Schubert matroids is proved by proving a convexity-like property for the number of bases of Schubert matroids. These numbers are summations of Kostka numbers and are intimately connected to combinatorial structures such as Young tableaux, lattice paths, etc., and for example, Catalan numbers appear as special cases.
Schubert matroids, on the one hand, are generalizations of the uniform matroid, and on the other, capture the combinatorics of fairly general lattice paths. Rapid mixing for many other combinatorial objects may be reduced to these. Thus, for example, the rapid-mixing of Schubert matroids subsumes the rapid mixing of the adjacency graph of triangulations of a convex \(n\)-gon.
Next, we show that the Markov chain associated with the general matroid has \(1- \lambda_2\geq {1\over p(n)2^{1.5r}}\), where \(n\) is the number of elements in the ground set and \(r\) \((\leq{n\over 2})\) is the rank of the matroid. Thus, for example, for a fixed \(r\), matroids are indeed rapid-mixing. This is the best result we know about general matroids. The proof constructs tight canonical paths indexed by sets of rank 1 less than the rank of the matroid. This comes out from a structural lemma for matroids about base exchange while maintaining ranks of the complements.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI