Erdős Problem #573 — Triangle-free and four-cycle-free extremal graphs
For a positive integer , let be the maximum number of edges in a simple graph on vertices containing neither a triangle nor a four-cycle as a subgraph. The question is whether, as tends to infinity through the positive integers,
equivalently, whether . 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 gives an edge scale of order , 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 , the maximum number of edges in a bipartite, -free graph on 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 and gives . Kövári, Sós, and Turán obtained the same asymptotic scale when 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 and forbidden. Bloom, Erdős Problem #573 Füredi and Simonovits, The history of degenerate (bipartite) extremal graph problems (2013)
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.