Problem 181

Let $Q_n$ be the $n$ -dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Prove that

R(Q_n) \ll 2^n.

Source: erdosproblems.com/181

Graph theory
Ramsey theory

Wiki page

Status

ClaimedProved

A full solution has been claimed but not yet accepted. The statement is true.

Open: the site labels the problem OPEN. The best bounds located in the search, whose scope the Current assessment records, are the trivial $R(Q_n)\ge2^n$ (a copy of $Q_n$ needs $2^n$ vertices) and Tikhomirov's $R(Q_n)\le2^{2n-cn+1}+2$ for all large $n$ with $c=0.03656$ (European J. Combin. 120 (2024), 103954, refereed; cited from the arXiv v3), that is $R(Q_n)\le2^{1.96344n+1}+2$ ; no proof of the linear bound, no counterexample, no preprint and no proof claim was found. This is a bounded negative finding, not a certificate of openness. After that search, the OpenAI release's preprint of 23 September 2026 claimed the linear bound $R(Q_n)\le C2^n$ in full; it is recorded on the claim page OpenAI 2026 as claimed, since it is unrefereed, unreviewed and has no Lean proof of the theorem, and the derived standing is claimed through that page.

Ti22: Tikhomirov, K., A remark on the Ramsey number of the hypercube. European J. Combin. 120 (2024), 103954, doi:10.1016/j.ejc.2024.103954 (Crossref record accessed: issue dated August 2024); arXiv:2208.14568 (v1 30 August 2022, v3 2 March 2024; 24 pages; the arXiv listing carries no journal reference). The site's text cites the arXiv number with the year 2022. Theorem 1.1, the Remark after it and Corollary 1.2, p. 2; Remark 1.3, p. 3. Library home: Tikhomirov 2024.
BuEr75: Burr, S. A. and Erdős, P., On the magnitude of generalized Ramsey numbers for graphs. Infinite and finite sets (Colloq., Keszthely, 1973), Vol. I, Colloq. Math. Soc. János Bolyai 10, North-Holland (1975), 215--240. The site's text prints no venue. The cube question, p. 239. Library home: Burr and Erdős 1975 (the Rényi archive scan).
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; Chapter V, problem 12, printed p. 346. The site cites p. 346. The survey writes $C^{(n)}$ for the page's $Q_n$ . Library home: Erdős 1993.
Er81: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Lecture Notes in Math. 885 (1981), 9--17. Not a site key; display (16') on p. 13. Library home: Erdős 1981 (a scan).
Le17: Lee, Choongbum, Ramsey numbers of degenerate graphs. Ann. of Math. (2) 185 (2017), 791--829; arXiv:1505.04773v2. The hypercube remark after Theorem 1.3, p. 4, and Section 7, p. 32. Library home: Lee 2017.
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. Two versions: the arXiv preprint (arXiv:1002.0045v1, 18 pages) and the journal text (23 pages). Its theorems are the bounded-degree bound $r(H)\le2^{c\Delta\log\Delta}n$ (Theorem 1.1, printed p. 515) and the induced Ramsey bound (Theorems 1.2--1.3, pp. 515--516); its Section 4 (pp. 532--533) is concluding remarks with no numbered statement, and neither version contains a Theorem 4.1, a bipartite theorem or a bound on $R(Q_n)$ anywhere in its text. The bound $R(Q_n)\le2^{2n+6}$ is [CFS16]'s, not this paper's. Library home: Conlon and Sudakov 2012.
CFS16: Conlon, D., Fox, J. and Sudakov, B., Short proofs of some extremal results II. J. Combin. Theory Ser. B 121 (2016), 173--196, doi:10.1016/j.jctb.2016.03.005; arXiv:1507.00547v2 (11 February 2016; the journal text is not held). Not a site key; it is the reference [4] of [Ti22] and the reference [11] of [Le17]. Theorem 4.1 and Corollary 4.2, preprint p. 7: "For every bipartite graph $H$ on $n$ vertices with maximum degree $\Delta$ , $r(H)\le2^{\Delta+6}n$ " and "For every positive integer $d$ , $r(Q_d)\le2^{2d+6}$ ". Library home: Conlon, Fox and Sudakov 2016.
HSZ26: Heath, E., Schwieder, C. and Zerbib, S., Generalized Ramsey numbers in the hypercube. arXiv:2601.15451v1 (21 January 2026), 12 pages; preprint. Context only: it bounds the coloring number $f(Q_n,C_k,q)$ , not $R(Q_n)$ . Library home: Heath and Zerbib 2026.
OAI26: OpenAI, The hypercube Ramsey number has linear order. Preprint of the OpenAI mathematics release, 23 September 2026 (paper.pdf at the release's pinned revision); not a site key; unrefereed; the release's Lean proves only its Lemma 2.1 and elementary bounds, not Theorem 1.1. Claims checked for Theorem 1.1, Lemma 2.1 and the staging statements of the proof; the proof read for structure only. Library home: OpenAI 2026; result page OpenAI 2026, Theorem 1.1. Claim page: OpenAI 2026.

Problem 181

Status

Proof claims

Discussion