{
  "id": "2308.16163",
  "version": "v1",
  "published": "2023-08-30T17:32:57.000Z",
  "updated": "2023-08-30T17:32:57.000Z",
  "title": "The extremal number of cycles with all diagonals",
  "authors": [
    "Domagoj Bradač",
    "Abhishek Methuku",
    "Benny Sudakov"
  ],
  "comment": "14 pages, comments welcome!",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1975, Erd\\H{o}s asked the following natural question: What is the maximum number of edges that an $n$-vertex graph can have without containing a cycle with all diagonals? Erd\\H{o}s observed that the upper bound $O(n^{5/3})$ holds since the complete bipartite graph $K_{3,3}$ can be viewed as a cycle of length six with all diagonals. In this paper, we resolve this old problem. We prove that there exists a constant $C$ such that every $n$-vertex with $Cn^{3/2}$ edges contains a cycle with all diagonals. Since any cycle with all diagonals contains cycles of length four, this bound is best possible using well-known constructions of graphs without a four-cycle based on finite geometry. Among other ideas, our proof involves a novel lemma about finding an `almost-spanning' robust expander which might be of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-30T17:32:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "extremal number",
      "complete bipartite graph",
      "diagonals contains cycles",
      "maximum number",
      "vertex graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}