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 language | English |
---|---|
Title of host publication | Proceedings 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13, New Orleans LA, USA, January 6-8, 2013) |
Place of Publication | Philadelphia PA |
Publisher | Society for Industrial and Applied Mathematics (SIAM) |
Pages | 675-694 |
ISBN (Print) | 978-1-611972-52-8 |
Publication status | Published - 2013 |
Event | 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) - Astor Crowne Plaza Hotel, New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 Conference number: 24 http://www.siam.org/meetings/da13/ |
Conference
Conference | 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) |
---|---|
Abbreviated title | SODA '13 |
Country/Territory | United States |
City | New Orleans |
Period | 6/01/13 → 8/01/13 |
Internet address |