{
  "id": "2401.04894",
  "version": "v1",
  "published": "2024-01-10T02:53:36.000Z",
  "updated": "2024-01-10T02:53:36.000Z",
  "title": "On degree powers and counting stars in $F$-free graphs",
  "authors": [
    "Dániel Gerbner"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a positive integer $r$ and a graph $G$ with degree sequence $d_1,\\dots,d_n$, we define $e_r(G)=\\sum_{i=1}^n d_i^r$. We let $\\mathrm{ex}_r(n,F)$ be the largest value of $e_r(G)$ if $G$ is an $n$-vertex $F$-free graph. We show that if $F$ has a color-critical edge, then $\\mathrm{ex}_r(n,F)=e_r(G)$ for a complete $(\\chi(F)-1)$-partite graph $G$ (this was known for cliques and $C_5$). We obtain exact results for several other non-bipartite graphs and also determine $\\mathrm{ex}_r(n,C_4)$ for $r\\ge 3$. We also give simple proofs of multiple known results. Our key observation is the connection to $\\mathrm{ex}(n,S_r,F)$, which is the largest number of copies of $S_r$ in $n$-vertex $F$-free graphs, where $S_r$ is the star with $r$ leaves. We explore this connection and apply methods from the study of $\\mathrm{ex}(n,S_r,F)$ to prove our results. We also obtain several new results on $\\mathrm{ex}(n,S_r,F)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-01-10T02:53:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "degree powers",
      "counting stars",
      "degree sequence",
      "connection"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}