Erdős Problem #181 — Ramsey number of the hypercube
For an integer , let be the graph with vertex set , in which two vertices are adjacent exactly when they differ in one coordinate. Thus and . For a graph , let be the least integer such that every red-blue coloring of the edges of the complete graph contains a monochromatic subgraph isomorphic to . The question is to prove that there is an absolute constant such that, for every ,
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 has exponentially many vertices and degree : 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 tends to infinity. The original trivial estimate follows from 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 ; work on density-based embedding results for degenerate graphs also gave a bound for sufficiently large . These improvements reduced the gap from the clique bound but remained far above a linear function of . Erdős Problems #181 Ramsey numbers of degenerate graphs
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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 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
- OpenAI-171-01-The-hypercube-Ramsey-number-has-linear-order.pdfOpen