A Method to construct the Sparse-paving Matroids over a Finite Set

2015/02/06 by Boris Mederos, Mederos, B., Martha Takane +5
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1502.01806

openalex publication_date 2015/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work we present an algorithm to construct sparse-paving matroids over finite set S. From this algorithm we derive some useful bounds on the cardinality of the set of circuits of any Sparse-Paving matroids which allow us to prove in a simple way an asymptotic relation between the class of Sparse-paving matroids and the whole class of matroids. Additionally we introduce a matrix based method which render an explicit partition of the r-subsets of S, \binomSr=\sqcup_i=1^γU_i such that each U_i defines a sparse-paving matroid of rank r.

Citations

• On the structure of the h-vector of a paving matroid

Related

• Enumerating matroids of fixed rank
• On the number of matroids compared to the number of sparse paving matroids
• Sparse paving matroids, basis-exchange properties, and cyclic flats
• Sparse Paving Positroids
• k-loose elements and k-paving matroids