← All problems

Erdős Problem #573 — Triangle-free and four-cycle-free extremal graphs

88 years old · traced to

For a positive integer nn, let ex(n;{C3,C4})\mathrm{ex}(n;\{C_3,C_4\}) be the maximum number of edges in a simple graph on nn vertices containing neither a triangle C3C_3 nor a four-cycle C4C_4 as a subgraph. The question is whether, as nn tends to infinity through the positive integers,

lim⁡n→∞ex(n;{C3,C4})(n/2)3/2=1,\lim_{n\to\infty}\frac{\mathrm{ex}(n;\{C_3,C_4\})}{(n/2)^{3/2}}=1,

equivalently, whether ex(n;{C3,C4})=(n/2)3/2+o(n3/2)\mathrm{ex}(n;\{C_3,C_4\})=(n/2)^{3/2}+o(n^{3/2}). On extremal numbers of the triangle plus the four-cycle, arXiv:2112.13689

Background

The problem belongs to the degenerate extremal graph setting: forbidding a bipartite cycle such as C4C_4 gives an edge scale of order n3/2n^{3/2}, and the triangle restriction asks whether the same leading constant as in the bipartite setting remains attainable. The study of this particular pair of forbidden cycles goes back to Erdős’s 1938 paper. A natural benchmark is the Zarankiewicz number z(n,C4)z(n,C_4), the maximum number of edges in a bipartite, C4C_4-free graph on nn vertices; such graphs are automatically triangle-free. On extremal numbers of the triangle plus the four-cycle, arXiv:2112.13689

The benchmark also appears in related results on the effect of forbidding odd cycles. Erdős and Simonovits proved that forbidding both C4C_4 and C5C_5 gives ex(n;{C4,C5})=(1+o(1))(n/2)3/2\mathrm{ex}(n;\{C_4,C_5\})=(1+o(1))(n/2)^{3/2}. Kövári, Sós, and Turán obtained the same asymptotic scale when C4C_4 and odd cycles of any length are forbidden. These results explain the proposed constant, but their additional odd-cycle restrictions do not give an upper bound for the problem with only C3C_3 and C4C_4 forbidden. Bloom, Erdős Problem #573 Füredi and Simonovits, The history of degenerate (bipartite) extremal graph problems (2013)

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.