Opened 6 years ago

Last modified 4 years ago

#18703 new enhancement

oriented matroids

Reported by: moritz Owned by: moritz
Priority: minor Milestone: sage-wishlist
Component: matroid theory Keywords:
Cc: stumpc5, Rudi, jipilab, yomcat, Stefan Merged in:
Authors: moritz Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by moritz)

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 6 years ago by stumpc5

  • Cc stumpc5 added

comment:2 Changed 6 years ago by Rudi

  • Cc Rudi added

comment:3 follow-up: Changed 5 years ago by moritz

  • Cc jipilab yomcat Stefan added
  • Description modified (diff)
  • Owner changed from (none) to moritz

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 5 years ago by Rudi

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 4 years ago by vdelecroix

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.