Erdős Problem #574 — Extremal numbers for consecutive odd and even cycles
For a family of graphs , let be the maximum number of edges in a simple graph on vertices that contains no subgraph isomorphic to any member of . Write for the cycle of length . The question is whether, for every fixed integer , as , Erdős Problems #574
Here the asymptotic is taken with fixed. Erdős Problems #574
Background
This is a problem of Erdős and Simonovits, recorded in 1982. Its forbidden family consists of two consecutive cycle lengths, one odd and one even. The reported constructions below are bipartite, so they automatically avoid the odd cycle as well as the specified even cycle. Erdős Problems #574
The case is the triangle-and-four-cycle problem. A 2021 paper describes its leading-constant question as widely open. It records the known estimate , where is the maximum number of edges in an -vertex bipartite graph with no four-cycle, and reports a lower bound exceeding this quantity by a positive term of order . That improvement is lower order than , so it does not itself settle the asymptotic asked for at . On extremal numbers of the triangle plus the four-cycle (2021)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.