Connectivity Properties of Matroids
Milena Mihail, Madhu Sudan · 1992
The bases-exchange graph of a matroid is the graph whose vertices are the bases of the matroid, and two bases are connected by an edge if and only if one can be obtained from the other by the exchange of a single pair of elements. In this paper we prove that a matroid is "connected" if and only if the "restricted bases-exchange graph" (the bases-exchange graph restricted to exchanges involving only one specic element e) is connected. This provides an alternative denition of matroid connectivity. Moreover, it shows that the connected components of the restricted bases-exchange graph satisfy a "ratios-condition", namely, that the ratio of the number of bases containing e to the number of bases not containing e is the same for each connected component of the restricted bases-exchange graph. We further show that if a more general ratios-condition is also true, namely, that any fraction of the bases containing e is adjacent to at least a fraction of the bases not containing e (where is any real number between 0 and 1), then the bases-exchange graph has the following expansion property: "For any bipartition of its vertices, the number of edges incident to both partition classes is at least as large as the size of the smaller partition". In fact, this was our original motivation for studying matroid connectivity, since such an expansion property yields efficient randomized approximation algorithms to count the number of bases of a matroid [18].