The method is_sparse_paving() of a matroid may be wrong!

[Xie]

for M in matroids.AllMatroids(8, type='sparse_paving'):
....:         print(M)

sparse_paving_n08_r04_#0: Matroid of rank 4 on 8 elements with 56 bases
sparse_paving_n08_r05_#0: Matroid of rank 5 on 8 elements with 48 bases
sparse_paving_n08_r06_#0: Matroid of rank 6 on 8 elements with 24 bases
sparse_paving_n08_r07_#0: Matroid of rank 7 on 8 elements with 8 bases
sparse_paving_n08_r07_#1: Matroid of rank 7 on 8 elements with 7 bases
sparse_paving_n08_r08_#0: Matroid of rank 8 on 8 elements with 1 bases

This can't be correct because almost all matroids are sparse paving.

In SageMath, the is_sparse_paving‘s Docstring defines:

*"Return if 'self' is sparse-paving.

A matroid is sparse-paving if the symmetric difference of every pair of circuits is greater than 2."*

I believe this is incorrect!

[Dima Pasechnik]

On Sat, Jan 25, 2025 at 11:03 PM Xie <xiehon...@gmail.com> wrote:
>
> for M in matroids.AllMatroids(8, type='sparse_paving'):
> ....: print(M)
> sparse_paving_n08_r04_#0: Matroid of rank 4 on 8 elements with 56 bases
> sparse_paving_n08_r05_#0: Matroid of rank 5 on 8 elements with 48 bases
> sparse_paving_n08_r06_#0: Matroid of rank 6 on 8 elements with 24 bases
> sparse_paving_n08_r07_#0: Matroid of rank 7 on 8 elements with 8 bases
> sparse_paving_n08_r07_#1: Matroid of rank 7 on 8 elements with 7 bases
> sparse_paving_n08_r08_#0: Matroid of rank 8 on 8 elements with 1 bases
>
> This can't be correct because almost all matroids are sparse paving.

this has been conjectured to be held asymptotically (i.e. as # n of
elements goes to infinity)
in https://doi.org/10.1016/j.ejc.2011.01.016
and https://www.sciencedirect.com/science/article/pii/S0196885812000802

With this in mind, it's hard to understand what exactly could be wrong
there (as this is something for n=8, not for n->oo)

>
> In SageMath, the is_sparse_paving‘s Docstring defines:
>
> *"Return if 'self' is sparse-paving.
>
> A matroid is sparse-paving if the symmetric difference of every pair of circuits is greater than 2."*
>
> I believe this is incorrect!

indeed, this seems strange, and no references are provided.
I've left a comment to this effect here:
https://github.com/sagemath/sage/pull/36962#issuecomment-2614537747

>
> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-support/a0f42d8e-a377-465e-b224-04166d86bc80n%40googlegroups.com.

[Xie]

Thank you. A matroid is sparse paving if both the matroid itself and its dual are paving. This criterion can be used to count the number of sparse paving matroids, assuming the .is_paving() method is correct. Sparse paving matroids have several definitions, but as far as I know, their definition is unambiguous.

[gmou3]

Hi Xie,

Thank you for noting this issue! Please check the newly merged changes where it has been corrected: https://github.com/sagemath/sage/pull/36962

I hadn't yet added the matroid-database package (and the AllMatroids method) back then.

[gmou3]

*

https://github.com/sagemath/sage/pull/39382