Ramsey theory asks how large a structure must be before some order is unavoidable — a monochromatic clique in a coloured graph, a monochromatic arithmetic progression, a solution to an equation inside one colour class. Exact Ramsey numbers are known only for small cases, so constructions (lower bounds) and SAT or flag-algebra certificates (upper bounds) can both be checked by machine.
Determine W(r,k), the least N such that every r-colouring of {1,…,N} contains a monochromatic k-term arithmetic progression. Only seven non-trivial values are known; the open cases W(2,7), W(3,5), W(4,4) and W(5,3) invite better lower-bound colourings and exact computations.
Narrow the gap 36 ≤ R(4,6) ≤ 40. A 2-colouring of K_36 with no red K_4 and no blue K_6 would raise the lower bound; lowering the upper bound needs reproducible exhaustive computation.
Narrow the gap between the known lower and upper bounds for R(5,5), currently 43 ≤ R(5,5) ≤ 46.
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then R(k)/k2^k/2→ ∞.
Let R(k,l) be the usual Ramsey number: the smallest n such that if the edges of K_n are coloured red and blue then there exists either a red K_k or a blue K_l. Prove the existence of some c>0 such that lim_k→ inftyR(k+1,k)/R(k,k)> 1+c. A problem of Erdős and Sós.
Erdős Problem 1167. Let r ≥ 2 be finite, γ ≥ 2, and λ be an infinite cardinal. Let κ_α > r be cardinals for all α < γ. Is it true that 2^λ → (κ_α + 1)_α < γ^r+1 implies λ → (κ_α)_α < γ^r? Here + means cardinal addition, so that κ_α + 1 = κ_α if κ_α is infinite. A problem of Erdős, Hajnal, and Rado.
Let G be a graph with chromatic number aleph_1. Is it true that there is a colouring of the edges with aleph_1 many colours such that, in any countable colouring of the vertices, there exists a vertex colour containing all edge colours? A problem of Erdős, Galvin, and Hajnal.
Is it true that in any 2-colouring of ℕ there exists an infinite set A such that all elements of A+A are the same colour? A conjecture of Owings [Ow74].
There exists some constant c>0 such that R(C_4,K_n) ≪ n^2-c. The prize of 100 is offered in [Er78] for a proof or disproof. This problem is #17 in Ramsey Theory in the graphs problem collection.
Is it true that in any finite colouring of ℕ there exist arbitrarily large finite A such that all sums and products of distinct elements in A are the same colour?
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) ≪ 2^n.
What is the smallest k such that ℝ^2 can be red/blue coloured with no pair of red points unit distance apart, and no k-term arithmetic progression of blue points with distance 1?
The Hadwiger–Nelson problem asks: How many colors are required to color the plane such that no two points at distance 1 from each other have the same color?
Show that R(3,k+1)-R(3,k)→∞ as k→ ∞. A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
Let m be sufficiently large and let G be a graph with m edges and no isolated vertices. Is the Ramsey number R(G) maximised when G is 'as complete as possible'?
Prove that R(C_k,K_n)=(k-1)(n-1)+1 for k≥ n≥ 3 (except when n=k=3). Asked by Erdős, Faudree, Rousseau, and Schelp. This problem is #18 in Ramsey Theory in the graphs problem collection.
Determine the Ramsey number R(C_4, S_n), where S_n=K_1,n is the star on n+1 vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
Let R_r(n) denote the r-uniform hypergraph Ramsey number: the minimal m such that if we 2-colour all edges of the complete r-uniform hypergraph on m vertices then there must be some monochromatic copy of the complete r-uniform hypergraph on n vertices.
Let F(n,α) denote the smallest m such that there exists a 2-colouring of the edges of K_n so that every X⊆ [n] with lvert Xrvert≥ m contains more than α C(lvert Xrvert, 2) many edges of each colour. Prove that, for every 0≤ α < 1/2, F(n,α)∼ c_αlog n for some constant c_α depending only on α.
Let R_3(n) be the minimal m such that if the edges of the 3-uniform hypergraph on m vertices are 2-coloured then there is a monochromatic copy of the complete 3-uniform hypergraph on n vertices. Is there some constant c>0 such that R_3(n) ≥ 2^2^cn?
Let G be such that any subgraph on k vertices has at most 2k-3 edges. Is it true that, if H has m edges and no isolated vertices, then R(G,H) ≪ m? In other words: if G is sparse (every induced subgraph on k vertices has ≤ 2k-3 edges), is G Ramsey size linear?
Erdős Problem 567 (Q3) Is Q_3 (the 3-dimensional hypercube) Ramsey size linear?
Let G be a graph such that R(G,T_n)≪ n for any tree T_n on n vertices and R(G,K_n)≪ n^2. Is it true that, for any H with m edges and no isolated vertices, R(G,H)≪ m? In other words, is G Ramsey size linear? This problem is #33 in Ramsey Theory in the graphs problem collection.
Let k≥ 1. What is the best possible c_k such that R(C_2k+1,H)≤ c_k m for any graph H on m edges without isolated vertices? This problem is #34 in Ramsey Theory in the graphs problem collection.
Determine which countable ordinals β have the property that, if α = ω^β, then in any red/blue colouring of the edges of K_α there is either a red K_α or a blue K_3.
Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G_1, G_2) is it true that (1) for every n ≥ 1 there is a graph H without a G_1 such that any n-colouring of H's edges contains a monochromatic G_2, and yet (2) for every graph H without a G_1 there is an aleph_0-colouring of H's edges…
Erdős Problem 598: Let m be an infinite cardinal and κ be the successor cardinal of 2^aleph_0. Can one colour the countable subsets of m using κ many colours so that every X ⊆ m with |X| = κ contains subsets of all possible colours?
Let f(n) be the minimal m such that if the edges of K_2^n+1 are coloured with n colours then there must be a monochromatic odd cycle of length at most m. Estimate f(n).
Erdős Problem 70: Let c be the order type of the real numbers, let β be a countable ordinal, and let 2 ≤ n < ω. Is it true that c → (β, n)^3_2? Note: The cases n ≤ 3 are trivially true (compare omega_three), so the genuine content of the conjecture begins at n = 4.
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then find the value of lim_k→ inftyR(k)^1/k. This problem is #3 in Ramsey Theory in the graphs problem collection.
Let R(k) be the Ramsey number for K_k. Give a constructive proof that R(k) > C^k for some constant C > 1. Equivalently, give an explicit construction of graphs on n vertices which contain no clique and no independent set of size ≥ c log n, for some constant c > 0.
Let c>0 and let f_c(n) be the maximal m such that every graph G with n vertices and at least cn^2 edges, where each edge is contained in at least one triangle, must contain a book of size m, that is, an edge shared by at least m different triangles. Estimate f_c(n).
Is it true that R(n+1)/R(n)≥ 1+c for some constant c>0, for all large n?
Is it true that, for all large n, f(n + 1) ≥ f(n)?
Let 0 < ε < 1. Is it true that, if k is sufficiently large, then R(G) > (1-ε)^k R(k) for every graph G with chromatic number χ(G)=k? The restriction ε < 1 excludes negative bases in (1-ε)^k. This problem is #12 in Ramsey Theory in the graphs problem collection.
Let S ⊆ ℝ be a set containing no solutions to a + b = c. Must there be a set A ⊆ ℝ ∖ S of cardinality continuum such that A + A ⊆ ℝ∖ S?
