Opened 7 years ago

Last modified 6 years ago

#18703 new enhancement

oriented matroids

Reported by: Moritz Firsching Owned by: Moritz Firsching
Priority: minor Milestone: sage-wishlist
Component: matroid theory Keywords:
Cc: Christian Stump, Rudi Pendavingh, Jean-Philippe Labbé, Michael Welsh, Stefan Merged in:
Authors: moritz Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Moritz Firsching)

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

Change History (5)

comment:1 Changed 7 years ago by Christian Stump

Cc: Christian Stump added

comment:2 Changed 7 years ago by Rudi Pendavingh

Cc: Rudi Pendavingh added

comment:3 Changed 6 years ago by Moritz Firsching

Cc: Jean-Philippe Labbé Michael Welsh Stefan added
Description: modified (diff)
Owner: set to Moritz Firsching

As a first idea, I propose to

  1. add a abstract OrientedMatroid? class as a child of the abstract Matroid class
  2. add a class OrientedBasisMatroid? as a subclass of the new OrientedMatroid? class
  3. (possibly add other OrientedMatroid? subclasses)
  4. 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?

comment:4 Changed 6 years ago by Rudi Pendavingh

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

comment:5 in reply to:  3 Changed 6 years ago by Vincent Delecroix

Replying to moritz:

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.

Note: See TracTickets for help on using tickets.