The Extremal Number of Cycles with All Diagonals

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⁵/³) holds since the complete bipartite graph K3,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 graph with at least Cn³/² 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.