{
  "id": "1912.00986",
  "version": "v1",
  "published": "2019-12-02T18:24:46.000Z",
  "updated": "2019-12-02T18:24:46.000Z",
  "title": "Stability and supersaturation of $4$-cycles",
  "authors": [
    "Jialin He",
    "Jie Ma",
    "Tianchi Yang"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we investigate extremal problems on the subject of the $4$-cycle $C_4$, which has played a heuristic important role in the development of extremal graph theory. As a milestone F\\\"uredi proved that the extremal number $ex(q^2+q+1, C_4)\\leq \\frac12 q(q+1)^2$ holds for $q\\geq 14$. This matches with the fundamental construction of Erd\\H{o}s-R{\\'e}nyi-S\\'os and Brown from finite geometry for prime powers $q$, thus providing one of the very rare exact results in the field. Our first result is a stability of F\\\"uredi's theorem. We prove that for all even $q$, every $(q^2+q+1)$-vertex $C_4$-free graph with at least $\\frac12 q(q+1)^2-\\frac12 q+o(q)$ edges must be a spanning subgraph of a unique polarity graph, which is constructed from a finite projective plane. Among others, this gives an immediate improvement on the upper bound of $ex(n,C_4)$ for infinite many integers $n$. A longstanding conjecture of Erd\\H{o}s and Simonovits states that every $n$-vertex graph with $ex(n,C_4)+1$ edges contains at least $(1+o(1))\\sqrt{n}$ copies of $C_4$. Building on the above stability, we obtain an exact result in this direction and thus confirm Erd\\H{o}s-Simonovits conjecture for an infinite sequence of integers $n$. In fact our result implies a stronger assertion that generally speaking, whenever $n\\gg \\ell$ in these circumstances, we can characterize the graphs achieving the $\\ell^{th}$ least number of $C_4$'s. This can be extended to more general settings, which provide enhancements on the supersaturation problem of $C_4$. We also discuss some related problems and formalize a conjecture on $ex(n,C_4)$, whose affirmation would disprove Erd\\H{o}s-Simonovits conjecture for general $n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-12-02T18:24:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "supersaturation",
      "conjecture",
      "extremal graph theory",
      "heuristic important role",
      "unique polarity graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}