Incidence matrices, geometrical bases, combinatorial prebases and matroids (Q1381811)

For a relation \(A\subseteq(C\times D)\), where \(C\), \(D\) are two finite sets, and an ordering \(\sigma\) of \(C\), the authors construct a matroid \(M(\sigma)\) on the set \(D\). For the relation \(A\) with the incidence matrix \(\widehat A\) they also define a geometrical basis with respect to \(F\), where \(F\) is a subset of the set of all circuits of the column matroid on \(\widehat A\). Geometrical bases are certain bases of this column matroid. The authors establish connections between the bases of matroids \(M(\sigma)\) and the geometrical bases of \(A\) with respect to \(F\). These connections give a combinatorial way of constructing bases of the column matroid on \(\widehat A\) using a subset \(F\) of its circuits. The authors also consider a matroid \(M\) and the incidence relation between what they call the extended circuits of \(M\) and the bases of \(M\). Applying the same technique, they obtain the matroids \(M(\sigma)\) on the set of bases of the matroid \(M\). In case of the incidence relation between vertices and edges of a graph, this technique yields a unique matroid, the usual matroid of the graph. Some particular relations are considered: a class of relations with a certain property (the \(T\)-property) and the relation of inclusion of chambers in simplices in an affine point configuration.