Generation of oriented matroids --- a graph theoretical approach (Q1349279)

The purpose of this article is to give new algorithms for generation of oriented matroids based on constructions of one element extensions of two graph representations. The tope graph of a rank \(r\) oriented matroid \(M\) is the graph with its topes as vertices and the pairs of topes containing a common rank \(r-1\) covector as edges. The cocircuit graph of \(M\) is the graph with its cocircuits as vertices and the pairs of cocircuits contained in a common rank 2 covector as edges. They correspond to the graph of adjacency of maximal cells and the 1-skeleton of the cell decomposition of the sphere in the representation by pseudospheres. The authors study on these 2 graphs the possible localizations (signature of vertices) which will produce all the one element extensions. For the tope graph, they show that the positive and negative parts of a localization are connected. For the cocircuit graph, they characterize completely the localizations. Based on these results they give different algorithms working for general rank and not needing the matroid to be uniform. The most efficient algorithm is obtained from localizations of cocircuit graphs. Finally, they found some close relations between their best algorithm and the recent algorithm of Bokowski and Guedes de Oliveira (based on generation of chirotopes) even though their constructions start with different ideas and datas.