The dependence graph for bases in matroids

AbstractThis paper discusses a certain graph, called the “dependence graph” (“the DPG”), that can be defined naturally for a given independent set in a matroid. We are mainly concerned with the DPG of bases, and we study what the DPG of a base tells about the matroid. We show that there is a nice connection between the DPG and duality, and between the DPG and connectivity for matroids. This leads to an algorithm for determining the connected components of a matroid. For two elements a and b in the same such component, and algorithm is given that finds a base B such that a ∉ B, b ∈ F and b is element of the unique circuit in B ∪ a