Problem 765

Give an asymptotic formula for $\mathrm{ex}(n;C_4)$ .

Source: erdosproblems.com/765

Graph theory
Turán numbers

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

The site labels the problem SOLVED (LEAN). The asymptotic formula is the 1966 theorem of Erdős, Rényi and Sós, recorded on the claim page Erdős, Rényi and Sós, proved independently the same year by Brown, recorded on the claim page Brown; the frontmatter standing is derived from these two accepted claims, and the label's Lean marker refers to the outside formalization of the asymptotic, linked on both claim pages, which this corpus has neither built nor audited.

Br66: Brown, W. G., On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 (1966), no. 3, 281--285; Section 3, pp. 284--285, the independent proof of the asymptotic. Not among the site's reference keys. Library home: Brown 1966.
Er38: P. Erdős, On sequences of integers no one of which divides the product of two others and on related problems. Tomsk. Gos. Univ. Ucen Zap. (1938), 74-82.
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. (1975), 3-14.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350. Chapter I, the $C_4$ asymptotic and displays (9) and (10), printed pp. 335--336: "Rényi, V.T. Sós and I proved that [7] $T(n;C_4)=\left(\tfrac12+o(1)\right)n^{3/2}$ ", the asymptotic formula asked here, reported as a theorem; then the conjecture (9) $T(p^2+p+1;C_4)=\tfrac12(p^3+p)+p^2+1$ for $p$ a power of a prime, "Füredi recently proved (9)", and the conjecture (10) $T(n;C_4)=\tfrac12n^{3/2}+\tfrac n4+O(n^{1/2})$ , repeated "with some trepidation". Library home: Erdős 1993.
Fu83: Füredi, Z., Graphs without quadrilaterals. J. Combin. Theory Ser. B (1983), 187-190.
MaYa23: Ma, Jie and Yang, Tianchi, Upper bounds on the extremal number of the 4-cycle. Bull. Lond. Math. Soc. (2023), 1655-1667.
Re58: Reiman, I., Über ein Problem von K. Zarankiewicz. Acta Math. Acad. Sci. Hungar. (1958), 269-273.

Problem 765

Status

Proof claims

Discussion