The Extremal Number of Cycles with All Diagonals

Abstract In 1975, Erd̋s asked the following question: What is the maximum number of edges that an n-vertex graph can have without containing a cycle with all diagonals? Erd̋s observed that the upper bound O (n^5/3) holds since the complete bipartite graph K₃, ₃ 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 graph with at least 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 four-cycles 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.