{
  "id": "1602.04763",
  "version": "v1",
  "published": "2016-02-15T18:50:27.000Z",
  "updated": "2016-02-15T18:50:27.000Z",
  "title": "On the number of bases of almost all matroids",
  "authors": [
    "Rudi Pendavingh",
    "Jorn van der Pol"
  ],
  "comment": "16 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "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(1/n)\\leq 1-b(M)\\leq O(\\log(n)^3/n)\\text{ as }n\\rightarrow \\infty$$ for asymptotically almost all matroids $M$ on $n$ elements. We derive that asymptotically almost all matroids on $n$ elements (1) have a $U_{k,2k}$-minor, whenever $k\\leq O(\\log(n))$, (2) have girth $\\geq \\Omega(\\log(n))$, (3) have Tutte connectivity $\\geq \\Omega(\\sqrt{\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-02-15T18:50:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05B35",
      "05A16",
      "94A17"
    ],
    "keywords": [
      "ground set",
      "tutte connectivity",
      "sparse paving matroids",
      "cardinality",
      "truncation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}