{
  "id": "1805.07520",
  "version": "v1",
  "published": "2018-05-19T06:01:33.000Z",
  "updated": "2018-05-19T06:01:33.000Z",
  "title": "Counting copies of a fixed subgraph in $F$-free graphs",
  "authors": [
    "Dániel Gerbner",
    "Cory Palmer"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Fix graphs $F$ and $H$ and let $ex(n,H,F)$ denote the maximum possible number of copies of the graph $H$ in an $n$-vertex $F$-free graph. The systematic study of this function was initiated by Alon and Shikhelman [{\\it J. Comb. Theory, B}. {\\bf 121} (2016)]. In this paper, we give new general bounds concerning this generalized Tur\\'an function. We also determine $ex(n,P_k,K_{2,t})$ and $ex(n,C_k,K_{2,t})$ asymptotically for every $k$ and $t$. For example, it is shown that for $t \\geq 2$ and $k\\geq 5$ we have $ex(n,C_k,K_{2,t})=\\left(\\frac{1}{2k}+o(1)\\right)(t-1)^{k/2}n^{k/2}$. We also characterize the graphs $F$ that cause the function $ex(n,C_k,F)$ to be linear in $n$. In the final section we discuss a connection between the function $ex(n,H,F)$ and so-called Berge hypergraphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-19T06:01:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "fixed subgraph",
      "counting copies",
      "systematic study",
      "fix graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}