On the number of matroids

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Downloads (Pure)

Abstract

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 log log m_n is at least n - 3/2 log n - O(1). On the other hand, Pi¿ (1973) showed that log log m_n = n - logn + log log n + 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 log log m_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 independent sets in the Johnson graph to give a compressed representation of matroids.
Original languageEnglish
Title of host publicationProceedings 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13, New Orleans LA, USA, January 6-8, 2013)
Place of PublicationPhiladelphia PA
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages675-694
ISBN (Print)978-1-611972-52-8
Publication statusPublished - 2013
Event24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) - Astor Crowne Plaza Hotel, New Orleans, United States
Duration: 6 Jan 20138 Jan 2013
Conference number: 24
http://www.siam.org/meetings/da13/

Conference

Conference24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
Abbreviated titleSODA '13
CountryUnited States
CityNew Orleans
Period6/01/138/01/13
Internet address

Fingerprint Dive into the research topics of 'On the number of matroids'. Together they form a unique fingerprint.

Cite this