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^{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 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. [ABSTRACT FROM AUTHOR]