On the Number of Bases of Almost All Matroids
On the Number of Bases of Almost All Matroids
复制标题
几乎所有拟阵的基数
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. V. D. Pol
中科院分区：
文献类型：
--
作者：
R. Pendavingh;J. V. D. Pol
对于n元秩为r的拟阵M，设B（M）表示M的基在基数为r的基集的子集中所占的比例.我们证明了$$\Omega \left（{1/n} \right）\leqslant 1 - B\left（M \right）\leqslant O\left（{\log {{\left（n \right）}^3}/n} \right）a\;sn \to \infty $$Ω（1/n）≤1−B（M）≤O（log（n）3/n）asn→∞对于几乎所有的n元拟阵M都是渐近的。我们证明了：（1）当k≤O（log（n））时，几乎所有的n元拟阵都有一个Uk，2k-子式;（2）围长≥Ω（log（n））;{（\sqrt {log（n）}）}$$≥Ω（log（n）），和（4）不出现作为另一个拟阵的截断。我们的论点是基于一个精炼的方法，用于编写任何给定拟阵的压缩描述，其允许相对于稀疏铺路拟阵的数量限制类中拟阵的数量。
For a matroid M of rank r on n elements, let b(M) denote the fraction of bases of M among the subsets of the ground set with cardinality r. We show that $$\Omega \left( {1/n} \right) \leqslant 1 - b\left( M \right) \leqslant O\left( {\log {{\left( n \right)}^3}/n} \right)a\;sn \to \infty $$Ω(1/n)≤1−b(M)≤O(log(n)3/n)asn→∞ for asymptotically almost all matroids M on n elements. We derive that asymptotically almost all matroids on n elements (1) have a Uk,2k-minor, whenever k≤O(log(n)), (2) have girth ≥Ω(log(n)), (3) have Tutte connectivity $$\geq\Omega\;{(\sqrt {log(n)})}$$≥Ω(log(n)), and (4) do not arise as the truncation of another matroid.Our argument is based on a refined method for writing compressed descriptions of any given matroid, which allows bounding the number of matroids in a class relative to the number of sparse paving matroids.