Paving matroids that are not sparse paving
The Mayhew--Newman--Welsh--Whittle conjecture predicts that asymptotically almost all matroids are sparse paving. We study the gap between paving and sparse paving matroids at the logarithmic scale. Let \(p_n\) be the number of paving matroids on \([n]\), let \(sp_n\) be the number of sparse paving matroids on \([n]\), and let \(sp_{n,r}\) be the number of rank-\(r\) sparse paving matroids on \([n]\). We prove that \[ p_n-sp_n\ge sp_{n,\lfloor n/2\rfloor}^{1-o(1)}. \] Thus the paving matroids that are not sparse paving are themselves logarithmically large. The construction prescribes one…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.11054
curl -X POST /api/v1/records/arxiv/2605.11054/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.11054/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'