← All problems

Erdős Problem #181 — Ramsey number of the hypercube

51 years old · traced to

For an integer n≥1n\ge 1, let QnQ_n be the graph with vertex set {0,1}n\{0,1\}^n, in which two vertices are adjacent exactly when they differ in one coordinate. Thus ∣V(Qn)∣=2n|V(Q_n)|=2^n and ∣E(Qn)∣=n2n−1|E(Q_n)|=n2^{n-1}. For a graph HH, let R(H)R(H) be the least integer NN such that every red-blue coloring of the edges of the complete graph KNK_N contains a monochromatic subgraph isomorphic to HH. The question is to prove that there is an absolute constant CC such that, for every n≥1n\ge 1,

R(Qn)≤C2n.R(Q_n)\le C2^n.

Erdős Problems #181 A remark on the Ramsey number of the hypercube

Background

The linear bound is the Burr–Erdős conjecture for the hypercube. The question is notable because QnQ_n has exponentially many vertices and degree nn: the conjecture asks for a Ramsey number bounded by a constant multiple of its vertex count, despite its increasing degree. Erdős later recalled that he and Sós had considered the problem but could not decide whether R(Qn)/2nR(Q_n)/2^n tends to infinity. The original trivial estimate follows from Qn⊆K2nQ_n\subseteq K_{2^n} and the general Ramsey bound for a clique, but is vastly larger than the conjectured scale. Erdős Problems #181 (BuEr75; Er93, p. 346)

An important intermediate approach was to seek embeddings in dense bipartite graphs, a setting that can be used to obtain Ramsey bounds. Conlon, Fox, and Sudakov used dependent random choice to obtain an upper bound of order 22n2^{2n}; work on density-based embedding results for degenerate graphs also gave a bound R(Qn)≤22n+n22nR(Q_n)\le 2^{2n}+n^2 2^n for sufficiently large nn. These improvements reduced the gap from the clique bound but remained far above a linear function of 2n2^n. Erdős Problems #181 Ramsey numbers of degenerate graphs

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI. Claims an absolute constant C with two-color Ramsey number R(Q_n)<=C 2^n for every binary-cube dimension n>=0.See full solutionHide full solution

Claimed by OpenAI.

Claims an absolute constant C with two-color Ramsey number R(Q_n)<=C 2^n for every binary-cube dimension n>=0.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-hypercube-Ramsey-number-has-linear-order-September-23-2026/paper.pdf

  • OpenAI-171-01-The-hypercube-Ramsey-number-has-linear-order.pdf1,424,109 bytesOpen