Iterator for paving matroids #35464
Assignees
Comments
5 tasks
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Jan 30, 2024
…driver function
<!-- ^^^^^
Please provide a concise, informative and self-explanatory title.
Don't put issue numbers in there, do this in the PR body below.
For example, instead of "Fixes sagemath#1234" use "Introduce new method to
calculate 1+1"
-->
<!-- Describe your changes here in detail -->
This enables the generation of all matroids of certain number of
elements (and, optionally, of certain rank or type). There exist
restrictions based on the underlying database (Yoshitake Matsumoto's
Database of Matroids: https://www-
imai.is.s.u-tokyo.ac.jp/~ymatsu/matroid/index.html). Note that the
database files consume ~75MB of space, which drops to ~1.5MB upon a
standard compression.
<!-- Why is this change required? What problem does it solve? -->
<!-- If this PR resolves an open issue, please link to it here. For
example "Fixes sagemath#12345". -->
<!-- If your change requires a documentation PR, please link it
appropriately. -->
Partially addresses sagemath#35464 (the type can be set to `paving`).
### 📝 Checklist
<!-- Put an `x` in all the boxes that apply. -->
<!-- If your change requires a documentation PR, please link it
appropriately -->
<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
<!-- Feel free to remove irrelevant items. -->
- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.
URL: sagemath#37140
Reported by: gmou3
Reviewer(s): Travis Scrimshaw
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Feb 1, 2024
…driver function
<!-- ^^^^^
Please provide a concise, informative and self-explanatory title.
Don't put issue numbers in there, do this in the PR body below.
For example, instead of "Fixes sagemath#1234" use "Introduce new method to
calculate 1+1"
-->
<!-- Describe your changes here in detail -->
This enables the generation of all matroids of certain number of
elements (and, optionally, of certain rank or type). There exist
restrictions based on the underlying database (Yoshitake Matsumoto's
Database of Matroids: https://www-
imai.is.s.u-tokyo.ac.jp/~ymatsu/matroid/index.html). Note that the
database files consume ~75MB of space, which drops to ~1.5MB upon a
standard compression.
<!-- Why is this change required? What problem does it solve? -->
<!-- If this PR resolves an open issue, please link to it here. For
example "Fixes sagemath#12345". -->
<!-- If your change requires a documentation PR, please link it
appropriately. -->
Partially addresses sagemath#35464 (the type can be set to `paving`).
### 📝 Checklist
<!-- Put an `x` in all the boxes that apply. -->
<!-- If your change requires a documentation PR, please link it
appropriately -->
<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
<!-- Feel free to remove irrelevant items. -->
- [x] The title is concise, informative, and self-explanatory.
- [x] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation accordingly.
URL: sagemath#37140
Reported by: gmou3
Reviewer(s): Travis Scrimshaw
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Is there an existing issue for this?
Problem Description
It is conjectured that asymptotically almost all matroids are paving matroids. Mederos, Pérez-Cabrera, Takane, Tapia-Sánchez, and Zavala provide an algorithm to construct all paving matroids of a given rank with groundset of a given size. This ticket aims to implement their algorithm and allow iteration over the set of all paving matroids.
Proposed Solution
Calling
matroids.PavingMatroids(n,k)should return a class (uniquely) representing the set of paving matroids on groundsets of sizenand rankk. It should have a__contains__method to test if a matroid is a paving matroid, and an__iter__method to support looping over all of them.Alternatives Considered
Alternatives could be to implement
matroids.PavingMatroid_n(n)to iterate over all paving matroids with a fixed groundset size and all ranks, and similarlymatroids.PavingMatroid_k(k).Additional Information
Algorithm is in https://arxiv.org/pdf/1906.04931.pdf.
The text was updated successfully, but these errors were encountered: