← All problems

Erdős Problem #574 — Extremal numbers for consecutive odd and even cycles

14 years old · documented by

For a family of graphs F\mathcal F, let ex(n;F)\mathrm{ex}(n;\mathcal F) be the maximum number of edges in a simple graph on nn vertices that contains no subgraph isomorphic to any member of F\mathcal F. Write CjC_j for the cycle of length jj. The question is whether, for every fixed integer k≥2k\ge 2, as n→∞n\to\infty, Erdős Problems #574

ex(n;{C2k−1,C2k})=(1+o(1))(n2)1+1/k.\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})=(1+o(1))\left(\frac n2\right)^{1+1/k}.

Erdős Problems #574

Here the asymptotic is taken with kk 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 k=2k=2 is the triangle-and-four-cycle problem. A 2021 paper describes its leading-constant question as widely open. It records the known estimate z(n,C4)=(n/2)3/2+o(n3/2)z(n,C_4)=(n/2)^{3/2}+o(n^{3/2}), where z(n,C4)z(n,C_4) is the maximum number of edges in an nn-vertex bipartite graph with no four-cycle, and reports a lower bound exceeding this quantity by a positive term of order n1.25n^{1.25}. That improvement is lower order than n3/2n^{3/2}, so it does not itself settle the asymptotic asked for at k=2k=2. On extremal numbers of the triangle plus the four-cycle (2021)

References

Progress summary

Never refreshed

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.