---

Claim. Sudakov, Ramsey numbers and the size of graphs (SIAM J. Discrete Math. 21 (2007), no. 4, 980--986), proves, as its abstract states the theorem, that for every $s\ge3$ there is a constant $c=c(s)>0$ such that every graph $G$ with $m$ edges satisfies

$$R(K_s,G)\ge c\left(\frac{m}{\log m}\right)^{\frac{s+1}{s+3}};$$

the abstract adds that the bound improves an earlier one of Erdős, Faudree, Rousseau and Schelp and is tight up to a polylogarithmic factor when $s=3$. In the letters of Problem 1182, take $s=3$, so the exponent is $2/3$: a connected graph $G$ on $n$ vertices with $f(n)$ edges and $R(K_3,G)=2n-1$ satisfies $c(f(n)/\log f(n))^{2/3}\le2n-1$, so $f(n)\le Cn^{3/2}\log f(n)\le2Cn^{3/2}\log n$, since $f(n)\le n^2$; that is,

$$f(n)=O\bigl(n^{3/2}\log n\bigr).$$

This one-line deduction from the stated theorem is made here; the paper does not mention the problem. With the 1980 lower bound $f(n)>An^{3/2}(\log n)^{1/2}$ of Burr, Erdős, Faudree, Rousseau and Schelp (Theorem 2, on their claim page), the exponent of $f(n)$ is $3/2$ and the two bounds differ by a factor $(\log n)^{1/2}$, replacing the 1980 upper bound $Bn^{5/3}(\log n)^{2/3}$. The same theorem with $s=m$ gives $f_m(n)=O(n^{1+2/(m+1)}\log n)$ for the $K_m$ version recorded on the problem page.

Covers. The upper bound on $f(n)$: the exponent $3/2$ is determined and the order of $f(n)$ is known to within a factor $(\log n)^{1/2}$. The exact order of $f(n)$, the function $F(n)$ and the closing question about $F(n)/n$ are not addressed; the closing question is answered no by the pending claim Brandt 1996, and the pending full claim Gu 2026 asserts that $f(n)$ has order $n^{3/2}(\log n)^{1/2}$, closing that gap.

Depends on. Nothing in this wiki; the deduction uses the paper's theorem and the definition of $f(n)$.

Acceptance. Refereed: SIAM Journal on Discrete Mathematics 21 (2007), no. 4, 980--986, DOI 10.1137/060667360, published online 12 December 2007 (the Crossref record dates the print issue January 2008). Not reviewed: the site's commentary does not cite the paper and its label is OPEN (page last edited 11 April 2026), so no curator credit exists and reviewed is not listed. The Zenodo record of the pending full claim of Gu cites the paper among its related identifiers.

Read depth. The paper is not held. The theorem is taken from the arXiv abstract (v1, 27 June 2007, the date this page is named by) and the publication data from the Crossref record; no page of the paper is compiled and the proof is not checked. The deduction above is the only step made here. Nothing here is independent review.