On the number of matroids

N. Bansal, R.A. Pendavingh, J.G. Pol, van der

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

14 Citaten (Scopus)
8 Downloads (Pure)

Samenvatting

We consider the problem of determining m n , the number of matroids on n elements. The best known lower bound on m n is due to Knuth (1974) who showed that loglogm n is at least n - 3/2logn - O(1). On the other hand, Piff (1973) showed that loglogm n = n - logn + loglogn + O(1), and it has been conjectured since that the right answer is perhaps closer to Knuth’s bound. We show that this is indeed the case, and prove an upper bound on loglogm n that is within an additive 1+o(1) term of Knuth’s lower bound. Our proof is based on using some structural properties of non-bases in a matroid together with some properties of stable sets in the Johnson graph to give a compressed representation of matroids.
Originele taal-2Engels
Pagina's (van-tot)253-277
Aantal pagina's25
TijdschriftCombinatorica
Volume35
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2015

Vingerafdruk Duik in de onderzoeksthema's van 'On the number of matroids'. Samen vormen ze een unieke vingerafdruk.

Citeer dit