Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. The Theorem (p. 123) of P. Erdős, On a theorem of Rademacher-Turán, Illinois J. Math. 6 (1962), no. 1, 122--127: there is an absolute constant c1>0c_1>0 such that for t<c1n/2t<c_1n/2 every graph on nn vertices with ⌊n2/4⌋+t\lfloor n^2/4\rfloor+t edges has at least t⌊n/2⌋t\lfloor n/2\rfloor triangles. The paper writes the edge count as f(n)+tf(n)+t with f(2m)=m2f(2m)=m^2 and f(2m+1)=m(m+1)f(2m+1)=m(m+1), that is f(n)=⌊n2/4⌋f(n)=\lfloor n^2/4\rfloor. On p. 122 the same paper records Rademacher's unpublished case t=1t=1 for even nn, states the conjecture for t<⌊n/2⌋t<\lfloor n/2\rfloor that Problem 1010 asks about, and shows that it fails at t=n/2t=n/2 for even n>4n>4. The page's date is the issue's, 1 March 1962 (Crossref; the reprint head reads Vol. 6, No. 1, March 1962).

Covers. The question for t<c1n/2t<c_1n/2, with c1c_1 not made explicit: for each fixed tt, every nn large in terms of tt. Not the range c1n/2≤t<⌊n/2⌋c_1n/2\le t<\lfloor n/2\rfloor, which Lovász and Simonovits settle.

Depends on. Nothing in this wiki; the paper's Theorem and its Lemmas 1--3 are the whole argument.

Acceptance. Refereed journal publication in the Illinois Journal of Mathematics, which is the refereed evidence. The site's label PROVED rests on Lovász and Simonovits and on Nikiforov and Khadzhiivanov, so the site's credit of the linear range to Erdős is not listed as reviewed. The proof (Lemmas 2--3 and pp. 124--127) is not examined in this corpus, and nothing here is independently reviewed.