Problem 546

Let $G$ be a graph with no isolated vertices and $m$ edges. Is it true that

R(G) \leq 2^{O(m^{1/2})}?

Source: erdosproblems.com/546

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved, the site's label (page last edited 18 November 2025), credited by the site's curator, T. F. Bloom, to Sudakov. Sudakov's Theorem 1.1 gives $r(G)\le2^{250\sqrt m}$ for every graph $G$ with $m$ edges and no isolated vertices (Adv. Math. 227 (2011), 601--609, refereed; arXiv:1002.0095v1). Alon, Krivelevich and Sudakov had proved the bipartite case with $2^{16\sqrt m+1}$ (Alon, Krivelevich and Sudakov 2003, a partial claim page) and the general bound $2^{7\sqrt m\log_2m}$ for all sufficiently large $m$ (Combin. Probab. Comput. 12 (2003), refereed). The claim page Sudakov 2010 records the theorem, its postings and the acceptance evidence, the curator's credit and the refereed publication; the frontmatter standing is derived from it.

Su11: Sudakov, B., A conjecture of Erdős on graph Ramsey numbers. Adv. Math. 227 (2011), no. 1, 601--609, doi:10.1016/j.aim.2011.02.004; arXiv:1002.0095v1 (30 January 2010; the only arXiv version). Theorem 1.1, p. 2 of the preprint. Library home: Sudakov 2011.
AKS03: Alon, N., Krivelevich, M. and Sudakov, B., Turán numbers of bipartite graphs and related Ramsey-type questions. Combin. Probab. Comput. 12 (2003), no. 5--6, 477--494, doi:10.1017/S0963548303005741 (page numbers of the published article). Conjecture 5.1 and Theorem 5.2, p. 487; Theorem 5.3, p. 488. Library home: Alon and Sudakov 2003.
Er84b: Erdős, P., On some problems in graph theory, combinatorial analysis and combinatorial number theory. Graph theory and combinatorics (Cambridge, 1983), Academic Press (1984), 1--17; the site cites p. 10. Library home: Erdős 1984 (the Rényi archive's scan 1984-11.pdf; display (14), p. 10, asks "Let $G$ be a graph of $e$ edges. Is it true that $r(G,G)<2^{c_1e^{1/2}}$ ?", and p. 11 adds that (14), if true, is best possible apart from $c_1$ ; the card carries the row for this problem).
ErGr75: Erdős, P. and Graham, R. L., On partition theorems for finite graphs. Colloq. Math. Soc. János Bolyai 10 (1975), 515--527; question (iv), p. 526, the source of the sharper Problem 545. Library home: Erdős and Graham 1975.

Problem 546

Status

Proof claims

Discussion