{
  "id": "1206.3211",
  "version": "v1",
  "published": "2012-06-14T18:57:04.000Z",
  "updated": "2012-06-14T18:57:04.000Z",
  "title": "Matchings and Independent Sets of a Fixed Size in Regular Graphs",
  "authors": [
    "Teena Carroll",
    "David Galvin",
    "Prasad Tetali"
  ],
  "comment": "13 pages. Appeared in Journal of Combinatorial Theory Series A in 2009",
  "categories": [
    "math.CO"
  ],
  "abstract": "We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size $\\ell$ in a $d$-regular graph on $N$ vertices. For $\\frac{2\\ell}{N}$ bounded away from 0 and 1, the logarithm of the bound we obtain agrees in its leading term with the logarithm of the number of matchings of size $\\ell$ in the graph consisting of $\\frac{N}{2d}$ disjoint copies of the complete bipartite graph $K_{d,d}$. This provides asymptotic evidence for a conjecture of S. Friedland {\\it et al.}. We also obtain an analogous result for independent sets of a fixed size in regular graphs, giving asymptotic evidence for a conjecture of J. Kahn. Our bounds on the number of matchings and independent sets of a fixed size are derived from bounds on the partition function (or generating polynomial) for matchings and independent sets.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-14T18:57:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C70",
      "05C35"
    ],
    "keywords": [
      "independent sets",
      "regular graph",
      "fixed size",
      "asymptotic evidence",
      "graph maximization problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.3211C"
    }
  }
}