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 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.
| Originele taal-2 | Engels |
|---|---|
| Titel | Proceedings 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13, New Orleans LA, USA, January 6-8, 2013) |
| Plaats van productie | Philadelphia PA |
| Uitgeverij | Society for Industrial and Applied Mathematics (SIAM) |
| Pagina's | 675-694 |
| ISBN van geprinte versie | 978-1-611972-52-8 |
| Status | Gepubliceerd - 2013 |
| Evenement | 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) - Astor Crowne Plaza Hotel, New Orleans, Verenigde Staten van Amerika Duur: 6 jan. 2013 → 8 jan. 2013 Congresnummer: 24 http://www.siam.org/meetings/da13/ |
Congres
| Congres | 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) |
|---|---|
| Verkorte titel | SODA '13 |
| Land/Regio | Verenigde Staten van Amerika |
| Stad | New Orleans |
| Periode | 6/01/13 → 8/01/13 |
| Ander | 24th Annual ACM-SIAM Symposium on Discrete Algorithms |
| Internet adres |