On the number of matroids
On the number of matroids
复制标题
关于拟阵的数量
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
J. V. D. Pol
中科院分区：
文献类型：
--
作者：
N. Bansal;R. Pendavingh;J. V. D. Pol
我们考虑确定n个元素上拟阵的个数Mn的问题。Knuth(1974)证明了Log Mn至少为n−3/2logn−O(1)。另一方面，Piff(1973年)证明了LogMn≤n−Logn+Logn+O(1)，并且由于正确解可能更接近Knuth界而被猜想.我们证明了这一点，并证明了LogMn的一个上界在Knuth下界的1+o(1)项的加性范围内.我们的证明是基于利用拟阵中非基的一些结构性质和Johnson图中稳定集的一些性质来给出拟阵的压缩表示。
We consider the problem of determining mn, the number of matroids on n elements. The best known lower bound on mn is due to Knuth (1974) who showed that loglogmn is at least n − 3/2logn − O(1). On the other hand, Piff (1973) showed that loglogmn ≤ 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 loglogmn 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.