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.
1047 shown· page 15 of 21
Let F be a family of sets closed under taking subsets (i.e. if B⊆ AinF then B∈ F). There exists some element x such that whenever F'⊆ F is an intersecting subfamily we have lvert F'rvert ≤ lvert A∈ F : x∈ Arvert.
Is it true that, for every bipartite graph G, there exists some α∈ [1,2) and c>0 such that ex(n;G)∼ cn^α? The condition that G have at least two edges excludes degenerate forbidden graphs whose extremal number is eventually zero, for which the displayed asymptotic with c>0 is impossible.
Is it true that ex(n; K_r,r) ≫ n^2-1/r?
If there is a finite projective plane of order n then must n be a prime power?
As n→ ∞ ranges over integers Σ_p≤ n1_n∈ (p/2,p)pmodp1/p∼ loglog n/2? A conjecture of Erdős, Graham, Ruzsa, and Straus [EGRS75]. By n∈ (p/2,p)pmodp we mean n≡ rpmodp for some integer r with p/2<r<p. The remainder n % p is computed in ℕ before casting to ℝ.
Let k ≥ 2. Does ((n+k)!)^2∣(2n)! hold for infinitely many n?
Let m be an infinite cardinal and G be a graph with chromatic number m. Let r≥ 1. Must G contain a subgraph of chromatic number m which does not contain any odd cycle of length ≤ r?
Murty-Simon Conjecture Let G be a graph on n vertices with diameter 2 such that deleting any edge increases the diameter. Is it true that G has at most ⌊ n^2 / 4 ⌋ edges? Equality is conjectured to hold for the complete balanced bipartite graph K_⌈ n/2 ⌉, ⌊ n/2 ⌋.
Let ε>0. Does there exist A⊆ ℕ such that the lower density of A+A is at least 1-ε and yet 1_Aast 1_A(n) ≪_ε 1 for all n?
Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?
What is the supremum of the set of admissible numbers?
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.
For every prime p, does the density of integers with h n = p exist?
What is the size of the largest Sidon subset A⊆1,2^2,…,N^2? Is it N^1-o(1)?
Is every proportionately dissociated (infinite) set the union of a finite number of dissociated sets?
Erdős Problem #779
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 ε > 0. Is there some set A⊂ℕ of density > 1 - ε such that a_1⋯ a_r = b_1⋯ b_s with a_i, b_j∈ A can only hold when r = s?
Let h(n) be maximal such that if A⊆ ℤ with lvert Arvert=n then there is B⊆ A with lvert Brvert ≥ h(n) such that if a_1+⋯+a_r=b_1+⋯+b_s with a_i,b_i∈ B then r=s. Estimate h(n).
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?
Erdős Problem #817
F(n) / log n → ∞ as n → ∞
Is it true that, for every ε>0, there exist infinitely many n such that g(n) > n^1-ε?
Are there infinitely many n such that, for all k≥ 1 τ(n + k) ≪ k?
Is it true that, for any a ∈ ℤ, there are infinitely many n such that φ(n) | n + a?
Erdős Problem 829 (open). Let A ⊆ ℕ be the set of perfect cubes. Is it true that (1_A ast 1_A)(n) ≪ (log n)^O(1)? That is, does there exist a natural number C such that the number of representations of n as a sum of two cubes is O((log n)^C) as n → ∞?
Erdos Problem 830, Part 1 We say that a,b∈ ℕ are an amicable pair if σ(a)=σ(b)=a+b. Are there infinitely many amicable pairs?
Does there exist a k>2 such that the k-sized subsets of 1,...,2k can be coloured with k+1 colours such that for every A⊂ 1,…,2k with lvert Arvert=k+1 all k+1 colours appear among the k-sized subsets of A?
Erdős Problem 839 (Part 1) [Er78f][Er92c]: Let 1 ≤ a_1 < a_2 < ⋯ be a strictly increasing sequence of positive integers such that no a_i is the sum of consecutive a_j for j < i. Is it true that limsup a_n / n = ∞?
Is it true that, for every integer t≥1, there is some integer a such that n choose k = a with 1≤ k ≤ n/2 has exactly t solutions?
Is it true that, for all large n, f(n + 1) ≥ f(n)?
Can there exist two distinct integers x and y such that x,y have the same prime factors, x+1,y+1 have the same prime factors, and x+2,y+2 also have the same prime factors?
Let d_n = p_n+1 - p_n, where p_n is the nth prime. Let r(x) be the smallest even integer t such that d_n = t has no solutions for n ≤ x. Is it true that r(x) → ∞?
Erdős Problem 855 (Segal's conjecture): π(x + y) ≤ π(x) + π(y) for all sufficiently large x, y, i.e. for all x, y ≥ N for some N.
Estimate m(n,k), or better give an asymptotic formula.
The density of the divisor sum set is asymptotically equivalent to c_1 / log(t)^c_2.
Let Q_n be the n-dimensional hypercube graph (so that Q_n has 2^n vertices and n2^n-1 edges). Is it true that every subgraph of Q_n with ≥ (1/2+o(1))n2^n-1 many edges contains a C_4?
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.
Erdős Problem 872, part (i) (weak form): there exists a constant ε > 0 such that the game length is at least ε · n for all sufficiently large n.
Let A = a_1 < a_2 < … ⊆ ℕ and let F(A,X,k) count the number of i such that [a_i,a_i+1, … ,a_i+k−1] < X, where the left-hand side is the least common multiple. Is it true that, for every ε > 0, there exists some k such that F(A,X,k) < X^ε?
Let A ⊂ ℕ be an additive basis of order k which is minimal in the sense that if B ⊂ A is any infinite set, then A B is not a basis of order k. Must there exist an infinite B ⊂ A such that A B is an additive basis of order k + 1?
For A⊆ 1,…,n let G(A) be the graph with vertex set A, where two integers are joined by an edge if they are coprime. Is it true that if |A| > ⌊ n/2 ⌋ + ⌊ n/3 ⌋ - ⌊ n/6 ⌋ then G(A) contains all odd cycles of length ≤ n/3 + 1? A problem of Erdős and Sárközy [ErSa97].
Is it true that, for every k ≥ 1, there exist integers N_1 < … < N_k such that |∩_i D(N_i)| ≥ k?
Let ε>0. Is it true that, for all large n, the number of divisors of n in (n^1/2,n^1/2+n^1/2-ε) is O_ε(1)? Erdős attributes this conjecture to Ruzsa.
Is there an absolute constant K such that, for every C > 0, if n is sufficiently large then n has at most K divisors in (n^1/2, n^1/2 + C n^1/4).
Let v(n,k) count the prime factors of n+k which do not divide n+i for 0≤ i < k. Is it true that v_0(n)=max_k≥ 0v(n,k)→ ∞ as n→ ∞?
Erdős [Er46] asked whether every set of n distinct points in ℝ^2 determines ≫ n/√(log n) many distinct distances.
If ω_k(n) counts the number of distinct prime factors of n which are >k, then is it true that, for every k≥ 1, liminf_n→ ∞Σ_0≤ i < kω_k(n+i)≤ k?
Let 2=p_1 < p_2 < ⋯ be the primes and k≥ 2. Is it true that, for all sufficiently large n, there must exist an integer in [n,n+p_1⋯ p_k) with >k many prime factors?
