Each problem states how progress is verified and what counts as a contribution. Besides the problems curated here, the catalogue includes open conjectures from Formal Conjectures (with Lean statements), optimization constants and the AlphaEvolve problems. Know one that belongs here? Propose a problem.
808 shown· page 6 of 17
Let κ be an uncountable cardinal. Must there exist a cardinal λ such that every graph with chromatic number λ contains a triangle-free subgraph with chromatic number κ? Shelah proved that a negative answer is consistent when κ = λ = aleph_1 (see erdos_1175.variants.aleph_one).
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.
Does there exist, for all r≥ 2, a basis A of order r (so that f_r(n)>0 for all large n) such that Σ_n≤ xf_r(n)^2 ≪ x for all x?
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].
Let A be an infinite set such that there are no distinct a,b,c ∈ A such that a | (b+c) and b,c > a. Is it true that ∑_n ∈ A 1/n < ∞?
Let A ⊆ ℝ be an infinite set. Must there be a set E ⊆ ℝ of positive measure which does not contain any set of the shape a * A + b for some a,b ∈ ℝ and a ≠ 0?
Is it true that for every ε,η>0 there exists a k such that the density of n for which P(n(n+1)⋯(n+k))>n^1-ε is at least 1-η (where P(m) is the greatest prime divisor of m)?
Prove that F(n)→ ∞ as n→ ∞.
Does 1,2^3,…,N^3 contain a Sidon set of size ≫ N?
Let P_d(n) be such that in any set of n points in ℝ^d there exist at least P_d(n) many points which do not contain an isosceles triangle. Estimate P_d(n) - in particular, is it true that P_2(n)<n^1-c for some constant c>0?
Are there n such that n+2^2^k is always squarefree?
Let A⊆ [1,n) be a set of integers such that (a,b)=1 for all distinct a,b∈ A. Is it true that Σ_a∈ A1/n-a≤ Σ_p < n1/p+O(1)?
Let G be the graph with vertex set those pairs (x,y)∈ ℕ^2 with gcd(x,y)=1, in which we join two vertices if the differ in only one coordinate, and there by ± 1. Is there a path going to infinity on G, say P, such that for all (x,y)∈ P both min(x,y)>1 and at least one of x or y is composite?
Let k ≠ 0 and 3≤ d_1 < d_2 < ⋯ < d_r be integers of gcd equal to 1 such that Σ_1 ≤ i ≤ rfrac 1d_i - 1 ≥ 1. Can all sufficiently large integers be written as a sum of the shape Σ_i c_ia_i where c_i ∈ 0, 1 and a_i is divisible by d_i ^ k and has only the digits 0, 1 when written in base d_i?
Let G be a graph with n vertices such that every induced subgraph on ≥ n/2 vertices has more than n^2/50 edges. Must G contain a triangle?
We say that N is powerful if whenever p| N we also have p^2| N. Let k≥ 3. Can the product of any k consecutive positive integers ever be powerful?
In [Er80] Erdős asks whether lim_k → ∞ (W(k))^1/k = ∞
Let A ⊆ ℕ. Let B ⊆ ℕ be the set of integers which are representable in exactly one way as the sum of two elements from A. Is it true that for all ε > 0 and large N, |1,…,N ∖ B| ≫_ε N^1/2 - ε?
Let k≥3. Are there k consecutive primes in arithmetic progression?
Prove an asymptotic formula for r_k(N), the largest possible size of a subset of 1, …, N that does not contain any non-trivial k-term arithmetic progression. That is, find f_k with r_k(N) / f_k(N) → 1 as N → ∞.
Does this imply that liminf |A ∩ [1,x]|/x = 0?
Let s_1 < s_2 < ⋯ be the sequence of squarefree numbers. Is it true that, for any α≥ 0, lim_x→∞ 1/xΣ_s_n≤ x(s_n+1-s_n)^α exists?
Let F(k) be the number of solutions to 1= 1/n_1+⋯+1/n_k, where 1≤ n_1<⋯<n_k are distinct integers. Find good estimates for F(k).
Is it true that Σ_n=1^∞(-1)^nn/p_n converges, where p_n is the sequence of primes? Note: In the problem statement, p_n is the n-th prime, indexed such that p_1=2, p_2=3, …. We 0-index here to reflect how Nat.nth works.
Let A be a finite Sidon set and A+A=s_1<⋯<s_t. Is it true that 1/tΣ_1≤ i<t(s_i+1-s_i)^2 → ∞ as lvert Arvert→ ∞?
Is it true that for every k ≥ 1 we have F(N + k) ≤ F(N) + 1 for all sufficiently large N?
Does there exist a maximal Sidon set A⊂ 1,…,N of size O(N^1/3)? A question of Erdős, Sárközy, and Sós [ESS94].
Let A be an infinite B₂[2] set. Must liminf |A ∩ 1, ..., N| * N ^ (- 1 / 2) = 0?
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.
Estimate h(n) by finding a better upper bound.
What is the limit F(N)/N as N → ∞?
Erdős Problem 17. Are there infinitely many cluster primes?
The problem is to determine the limit of the sequence F(N)/√(N) as N → ∞.
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?
Conjecture 1. Are there infinitely many practical numbers m such that h(m) < (log log m)^O(1)? More precisely: does there exist a constant C > 0 such that for infinitely many practical numbers m, we have h(m) < (log log m)^C?
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.
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
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?
If G is an edge-disjoint union of n copies of K_n, then is χ(G) = n?
What is the largest k such that in any permutation of ℤ there must exist a monotone k-term arithmetic progression x_1 < ⋯ < x_k? Here a permutation of ℤ is a one-sided arrangement a_1, a_2, a_3, … of the integers, i.e.
Must every permutation of ℕ, contain a monotone 4-term arithmetic progression?
Can ℕ be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions?
Does the longest arithmetic progression of primes in 1,…,N have length o(log N)?
Is there an integer m with (m, 6) = 1 such that none of 2^k · 3^ℓ · m + 1 are prime, for any k, ℓ ≥ 0?
Let s_1 < s_2 < … be the sequence of squarefree numbers. Is it true that for any ε > 0 and large n, s_n+1 - s_n ≪_ε s_n^ε?
Is there a dense subset of ℝ^2 such that all pairwise distances are rational?
Let n ≥ 4. Are there n points in ℝ^2, no three on a line and no four on a circle, such that all pairwise distances are integers?
Can every triangle-free graph on 5n vertices be made bipartite by deleting at most n^2 edges?
A conjecture by Heath-Brown: The sum of squares of the first N gaps between consecutive primes behaves like N * (log N)^2.
Is it true that for all c ≥ 0, the density f c of integers for which (p (n + 1) - p n) / log n < c exists and is a continuous function of c?
