Milena Mihail and Madhu Sudan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-92-662

, 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-662.pdf

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. <p>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 specific element <i>e</i>) is connected. This provides an alternative definition 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 <i>e</i> to the number of bases not containing <i>e</i> 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 alpha of the bases containing <i>e</i> is adjacent to at least a fraction alpha of the bases not containing <i>e</i> (where alpha 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 partion". 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.

---

BibTeX citation:

@techreport{Mihail:CSD-92-662,
    Author= {Mihail, Milena and Sudan, Madhu},
    Title= {Connectivity Properties of Matroids},
    Year= {1992},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6143.html},
    Number= {UCB/CSD-92-662},
    Abstract= {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. <p>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 specific element <i>e</i>) is connected. This provides an alternative definition 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 <i>e</i> to the number of bases not containing <i>e</i> 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 alpha of the bases containing <i>e</i> is adjacent to at least a fraction alpha of the bases not containing <i>e</i> (where alpha 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 partion". 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.},
}

EndNote citation:

%0 Report
%A Mihail, Milena 
%A Sudan, Madhu 
%T Connectivity Properties of Matroids
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-662
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6143.html
%F Mihail:CSD-92-662