Problem 565

Let $R^*(G)$ be the induced Ramsey number: the minimal $m$ such that there is a graph $H$ on $m$ vertices such that any $2$ -colouring of the edges of $H$ contains an induced monochromatic copy of $G$ .

Is it true that

R^*(G) \leq 2^{O(n)}

for any graph $G$ on $n$ vertices?

Source: erdosproblems.com/565

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED, and the frontmatter standing derives as solved from the claim page named below. The answer is yes: Theorem 1.1 of Aragão, Campos, Dahia, Filipe and Marciano gives a constant $C>0$ with $R^*(G)\le2^{Cn}$ for every graph $G$ on $n$ vertices, and their Theorem 1.2 gives $r^{Crn}$ for $r$ colors. The status-defining source is an arXiv paper (v2, 13 November 2025); the site's curator, T. F. Bloom, labels the problem PROVED and credits the paper, and Morris, whom the authors thank for reading the paper, reports the result as proved, with a proof outline, in the published text of his plenary lecture at the 2026 International Congress of Mathematicians. No independent review and no formal verification were found. The earlier bounds, $2^{O(n(\log n)^2)}$ (Kohayakawa, Prömel and Rödl; an explicit host by Fox and Sudakov) and $2^{O(n\log n)}$ (Conlon, Fox and Sudakov, refereed), are recorded below as history. The claim page Aragão, Campos, Dahia, Filipe and Marciano 2025 records the theorem, its postings and its acceptance evidence, and the frontmatter standing derives from it.

ACDFM25: Aragão, L., Campos, M., Dahia, G., Filipe, R. and Marciano, J. P., An exponential upper bound for induced Ramsey numbers. arXiv:2509.22629 (v1 26 September 2025; v2 13 November 2025, 59 pages). Library home: Aragão 2025.
Mo26: Morris, R., Some recent results in Ramsey theory. Proceedings of the International Congress of Mathematicians 2026, Vol. 2: Plenary Lectures, 210--239, doi:10.1137/25m1833369 (online 13 July 2026); arXiv:2601.05221v1 (8 January 2026). Theorem 1.5. Library home: Morris 2026.
CFS12: Conlon, D., Fox, J. and Sudakov, B., On two problems in graph Ramsey theory. Combinatorica 32 (2012), no. 5, 513--535, doi:10.1007/s00493-012-2710-3; arXiv:1002.0045v1 (30 January 2010, the version whose page numbers the locators below use). Theorem 1.2, arXiv p. 3 = printed p. 515; Theorem 1.3, arXiv p. 3 = printed p. 516; the two statements are the same in both versions. Library home: Conlon and Sudakov 2012; result page Theorem 1.2.
FoSu08: Fox, J. and Sudakov, B., Induced Ramsey-type theorems. Adv. Math. 219 (2008), no. 6, 1771--1800, doi:10.1016/j.aim.2008.07.009; arXiv:0706.4112v3 (27 December 2007). Corollaries 1.5 and 1.6, Theorem 1.7. Library home: Fox and Sudakov 2008.
KPR98: Kohayakawa, Y., Prömel, H. J. and Rödl, V., Induced Ramsey numbers. Combinatorica 18 (1998), no. 3, 373--404, doi:10.1007/PL00009828 (received 10 October 1997, per p. 373). Problem 1, p. 374; Theorem 3 and the diagonal remark, p. 375; concluding remarks, p. 402. Library home: Kohayakawa and Rödl 1998; result page Theorem 3. [FoSu08], [CFS12] and [ACDFM25] state the same bound.
EHP75: Erdős, P., Hajnal, A. and Pósa, L., Strong embeddings of graphs into colored graphs. Infinite and finite sets (Colloq., Keszthely, 1973), Vol. I, Colloq. Math. Soc. János Bolyai 10, North-Holland (1975), 585--595. Library home: Erdős and Pósa 1975.
De75: Deuber, W., Generalizations of Ramsey's theorem. Infinite and finite sets (Colloq., Keszthely, 1973), Vol. I, Colloq. Math. Soc. János Bolyai 10, North-Holland (1975), 323--332. Not held. Cited as [EHP75] and [ACDFM25] cite it.
Ro73: Rödl, V., The dimension of a graph and generalized Ramsey theorems. Thesis, Charles University, Prague (1973). Not held. The site credits it with the existence of $R^*(G)$ and with the bipartite case.
Er75d: Erdős, P., Problems and results on finite and infinite graphs. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) (1975), 183--192. Site source key; no library home; not consulted here. [ACDFM25] (p. 2) dates the conjecture "first implicitly in 1975 and then explicitly in 1984".

Problem 565

Status

Proof claims

Discussion