oriented matroids

[mo271]

Currently the Matroid class does not provide oriented matroids. I propose to implement oriented matroids, so that we can handle:

• the properties of the underlying unoriented matroid
• the positive and negative elements
• a representation of the chirotope functions
• checking if the input really is a
• checking if it is uniform
• giving out the face lattice
• duality
• ...

It should be possible to construct OMs from:

• directly formulations as:

  • oriented bases of vector configuration
  • covectors
  • cocircuits
  • chirotopes

• matrices (point configurations) over ordered fields

• directed Graphs

• hyperplane arrangements

• polytopes

CC: @stumpc5 @sagetrac-Rudi @jplab @sagetrac-yomcat @sagetrac-Stefan

Component: matroid theory

Author: moritz

Issue created by migration from https://trac.sagemath.org/ticket/18703

[mo271]

Description changed:

--- 
+++ 
@@ -1,10 +1,27 @@
 Currently the Matroid class does not provide oriented matroids.
-I propose to implement a base class oriented matroids, that provides:
+I propose to implement oriented matroids, so that we can handle:

-- the usual basic functions, like rank etc.
+
+- the properties of the underlying unoriented matroid
+- the positive and negative elements
 - a representation of the chirotope functions
+- checking if the input really is a 
 - checking if it is uniform
 - giving out the face lattice
-- ...
+- duality
+- ... 

-This could then for example be used to add an appropriate function to the Polyhedron class.
+It should be possible to construct OMs from:
+
+- directly formulations as:
+  - oriented bases of vector configuration
+  - covectors
+  - cocircuits
+  - chirotopes
+
+- matrices (point configurations) over ordered fields
+- directed Graphs
+- hyperplane arrangements
+- polytopes
+
+

[mo271]

comment:3

As a first idea, I propose to

a. add a abstract OrientedMatroid class as a child of the abstract Matroid class b. add a class OrientedBasisMatroid as a subclass of the new OrientedMatroid class c. (possibly add other OrientedMatroid subclasses) d. add a constructor function OrientedMatroid similar to the Matroid Conctructor, that can handle the various inputs

Perhaps its best to make this ticket a meta ticket and open new tickets for the points mentioned above. What do you think of the plan?

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:4

Hi Moritz,

I really like the plan.

1) The OrientedBasisMatroid class perhaps should be a subclass of BasisMatroid (or BasisExchangeMatroid) as well as OrientedMatroid; otherwise you have to do a extra work for each method already supported by BasisMatroid. For example, there is code for enumerating (unoriented) circuits in BasisExchangeMatroid. You don't want to repeat that code, I guess.

2) we use plain python sets in the Matroid interface to communicate subsets of the ground set. What will you use for the oriented sets, dictionaries or pairs of sets? I can imagine that the former is a lot faster as making pairs is a bit expensive, but I haven't tested it.

Cheers, Rudi

[videlec]

comment:5

Replying to @mo271:

Perhaps its best to make this ticket a meta ticket and open new tickets for the points mentioned above.

+1 would be easier to follow activity and reviews.