Problem 1182

Let $f(n)$ be maximal such that there is a connected graph $G$ with $n$ vertices and $f(n)$ edges such that

R(K_3,G)= 2n-1.

Let $F(n)$ be maximal such that every connected graph $G$ with $n$ vertices and $\leq F(n)$ edges has

R(K_3,G)= 2n-1.

Estimate $f(n)$ and $F(n)$ . In particular, is it true that $F(n)/n\to \infty$ ?

Source: erdosproblems.com/1182

Graph theory
Ramsey theory

Wiki page

Status

ClaimedAnswered

A full solution has been claimed but not yet accepted. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Open, in the site's label, which attaches to the estimation problem: subject to Brandt's pending bound, $F(n)$ is known to within a constant factor, between $17n/15$ and $84n$ for large $n$ , but not asymptotically, and $f(n)$ is not known to within a constant factor, its bounds being $n^{3/2}(\log n)^{1/2}$ and $n^{3/2}\log n$ up to constants, a factor $(\log n)^{1/2}$ apart. The closing question has the answer no if a 1996 preprint of Brandt is right that $F(n)<84n$ for all large $n$ , so $F(n)/n$ is bounded; the source is a preprint (Freie Universität Berlin, Preprint A 96-24), read in a converted copy that the library does not hold, and the site's commentary says that it answers the final question in the negative under the label OPEN, which is not acceptance, so the bound is a pending partial claim. The frontmatter's standing is derived from the claim pages, and the pending negative answer to the closing question is recorded here. The bounds the sources state are

\frac{17n+1}{15}\le F(n)<84n,\qquad An^{3/2}(\log n)^{1/2}<f(n)<Bn^{5/3}(\log n)^{2/3},

the lower bound on $F$ for all $n\ge4$ and the other three for large $n$ (Burr, Erdős, Faudree, Rousseau and Schelp 1980, Ars Combin., refereed, an accepted partial claim on its claim page (Burr, Erdős, Faudree, Rousseau and Schelp, 1980); Brandt 1996, preprint; Brandt's bound and the site's note on it are recorded on its claim page (Brandt, 1996)). The upper bound on $f(n)$ is superseded by Sudakov's theorem of 2007 (SIAM J. Discrete Math., refereed; not held, its statement as its arXiv abstract gives it): for $s\ge3$ every graph $G$ with $m$ edges has $R(K_s,G)\ge c(m/\log m)^{(s+1)/(s+3)}$ , so with $s=3$ a connected $n$ -vertex graph with $f(n)$ edges and $R(K_3,G)=2n-1$ has $c(f(n)/\log f(n))^{2/3}\le2n-1$ , whence $f(n)=O(n^{3/2}\log n)$ ; the exponents meet and the gap is the factor $(\log n)^{1/2}$ . The bound is recorded as an accepted partial claim on its claim page (Sudakov, 2007). Two proof claims of September 2026 on the site's tab, a full claim by Qiyuan Gu asserting the order of $f(n)$ (Gu 2026) and a partial claim by Pravar Kataria tightening the constants for $F(n)$ (Kataria 2026), are recorded on their claim pages; both are unreviewed, and the frontmatter's claimed standing is derived from the pending full claim.

BEFRS80: Burr, S. A., Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., An extremal problem in generalized Ramsey theory. Ars Combin. 10 (1980), 193--203. Definitions p. 193; Table I p. 194; Theorems 1 and 2 p. 198; Theorem 3 and the Question p. 202. Library home: Burr 1980.
Br96: Brandt, S., Expanding graphs and Ramsey numbers. Preprint No. A 96-24, Serie A Mathematik, Freie Universität Berlin, December 1996, 10 pp. Pp. 3--4 and 7--8. The copy read is a Ghostscript conversion of the preprint's PostScript, which the library does not hold.
Er78: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), Congressus Numerantium XXI (1978), 29--40; Section 4, printed pp. 33--34. Library home: Erdős 1978.
Cl77: Clancy, M., Some small Ramsey numbers. J. Graph Theory 1 (1977), 89--91; [FRS] Faudree, R. J., Rousseau, C. C. and Schelp, R. H., All triangle-graph Ramsey numbers for connected graphs of order six (listed in [BEFRS80] as "to appear in J. Graph Theory"). Neither held; the values of Table I for $n=5$ and $n=6$ are attributed to them by [BEFRS80], p. 195.
Sp77: Spencer, J., Asymptotic lower bounds for Ramsey functions. Discrete Math. 20 (1977), no. 1, 69--76, DOI 10.1016/0012-365X(77)90044-9. Theorem 2.1, printed p. 72 (PDF p. 4 of the publisher's open-archive scan), " $R(3,t)\ge(c-o(1))(t/\ln t)^2$ , $c=1/27$ ", the input of [BEFRS80]'s Theorem 1(b) (its display (2)) and, through the local-lemma reduction (1) on p. 73 (PDF p. 5) that proves it, of the upper bound of its Theorem 2. Library home: Spencer 1977; paged at Spencer 1977, Theorem 2.1 and Spencer 1977, Theorem 1.1 (Lovász).
AKS80: Ajtai, M., Komlós, J. and Szemerédi, E., A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), no. 3, 354--360, DOI 10.1016/0097-3165(80)90030-8. The input of the lower bound of [BEFRS80]'s Theorem 2 (which [BEFRS80] cite from the same authors' Sidon-sequence paper, their [1]): Theorem 3, printed p. 358 (PDF p. 5 of the publisher's open-archive scan), $R(3,x)<100x^2/\ln x$ . Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 3.
Su07: Sudakov, B., Ramsey numbers and the size of graphs. SIAM J. Discrete Math. 21 (2007), no. 4, 980--986, DOI 10.1137/060667360 (published online 12 December 2007); arXiv:0706.4102 (v1, 27 June 2007). The lower bound $R(K_s,G)\ge c(m/\log m)^{(s+1)/(s+3)}$ for every graph $G$ with $m$ edges, $s\ge3$ , as the abstract states it; the paper is not held and its proof is not checked.
BBH98: Brandt, S., Brinkmann, G. and Harmuth, T., All Ramsey numbers $r(K_3,G)$ for connected graphs of order 9. Electron. J. Combin. 5 (1998), R7. Not held; a lead cited in the thread comment of 28 September 2026 for the exact values of both functions through $n=12$ .

Problem 1182

Status

Proof claims

Discussion