{
  "id": "1812.01832",
  "version": "v1",
  "published": "2018-12-05T06:46:30.000Z",
  "updated": "2018-12-05T06:46:30.000Z",
  "title": "The maximum number of cliques in graphs without large matchings",
  "authors": [
    "Jian Wang"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given two graphs $T$ and $F$, the maximum number of copies of $T$ in an $F$-free graph on $n$ vertices is denoted by $ex(n,T,F)$ and is called the Generalized Tur\\'{a}n number. When $T=K_2$, it reduces to the classical Tur\\'{a}n number $ex(n,F)$. In 1961, Erd\\H{o}s and Gallai proved that \\[ ex(n,M_{k+1})=\\max\\left\\{\\binom{2k+1}{2}, \\binom{k}{2}+k(n-k)\\right\\}, \\] where $M_{k+1}$ is a matching of size $k+1$. In this note, we prove that for any $s\\geq 2$, \\[ ex(n,K_s,M_{k+1})=\\max\\left\\{\\binom{2k+1}{s}, \\binom{k}{s}+(n-k)\\binom{k}{s-1}\\right\\}. \\]",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-12-05T06:46:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum number",
      "large matchings",
      "free graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}