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 14 of 21
Let r≥ 2 and suppose that A⊆1,…,N is such that, for any m, there are at most r solutions to m=pa where p is prime and a∈ A. Give the best possible upper bound for Σ_n∈ A1/n. Erdős observed that Σ_n∈ A1/n≪ rlog N/loglog N, and the order Θ_r(log N / loglog N) is known (see erdos_538.matching_order).
Let h(n) be maximal such that, for any set A⊆ ℕ of size n, the set a/(a,b): a,b∈ Ahas size at least h(n). Estimate h(n).
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.
Show that for k≥ 3 ex(n;C_2k)≫ n^1+1/k. This problem is #46 in Extremal Graph Theory in the graphs problem collection.
Let δ > 0. If n is sufficiently large and G is a graph on n vertices with no K_2,2,2 (the octahedron) and at least δ n^2 edges, must G contain an independent set of size ≫_δ n? This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83].
Every connected graph on n vertices can be partitioned into at most ⌈ n/2⌉ edge-disjoint paths. A problem of Erdős and Gallai.
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 593 (\500): Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number > aleph_0. The answer is the set of obligatory finite 3-uniform hypergraphs, represented here on the labelled vertex sets Fin n.
Erdős Problem 595 (\250): Is there an infinite graph G which contains no K_4 and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
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?
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
Let r ≥ 2. Is it true that e(n,r+1) - e(n,r) → ∞ as n → ∞?
Does every almost-disjoint family of countably infinite sets whose pairwise intersections all have size ≠ 1 have Property B? Formally: let α be any type, let (A_i)_i ∈ I be a family of countably infinite subsets of α such that for all i ≠ j, the intersection A_i ∩ A_j is finite and |A_i ∩ A_j| ≠ 1.
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).
The Erdős–Hajnal Conjecture states that there is a constant c(H) > 0 for each H such that we can take f(n) = n^c(H) in the above formulation.
Let r≥ 3. If the edges of K_r^2+1 are r-coloured then there exist r+1 vertices with at least one colour missing on the edges of the induced K_r+1. In other words, there is no balanced colouring. A conjecture of Erdős and Gyárfás [ErGy99].
Let X be a set of cardinality aleph_ω and f be a function from the finite subsets of X to X such that f(A)not∈ A for all A. Must there exist an infinite Y⊆ X that is independent - that is, for all finite B⊂ Y we have f(B)not∈ Y?
Let X be a finite set of size n and H(n) be such that there is a function f:A : A⊆ X→ X so that for every Y⊆ X with lvert Yrvert ≥ H(n) we have f(A) : A⊆ Y=X. Prove that H(n)-log_2 n → ∞.
Let G be a graph with chromatic number k containing no K_k. If a,b≥ 2 and a+b=k+1 then must there exist two disjoint subgraphs of G with chromatic numbers ≥ a and ≥ b respectively?
Does every finite graph with minimum degree at least 3 contain a cycle of length 2^k for some k ≥ 2?
Let τ(n) count the number of divisors of n. Is there some n > 24 such that max_m < n(m + τ(m)) ≤ n + 2?
Is the sum Σ1/a_i minimised when G is a complete bipartite graph? This problem is #65 in Extremal Graph Theory in the graphs problem collection.
Let x_1,…,x_n∈ ℝ^2 and let R(x_i)=\# lvert x_j-x_irvert : j≠ i, where the points are ordered such that R(x_1)≤ ⋯ ≤ R(x_n). Let g(n) be the maximum number of distinct values the R(x_i) can take. Is it true that g(n) ≥ (1-o(1))n?
Is there and A ⊂ ℕ is such that lim_n→ ∞1_Aast 1_A(n)/log n exists and is ≠ 0?
Let x_1, …, x_n ∈ ℝ^3 be the vertices of a convex polyhedron. Are there at least (1 - o(1)) n/2 many distinct distances between the x_i?
Can the product of an arithmetic progression of positive integers n, n + d, ..., n + (k - 1)d of length k ≥ 4, with (n, d) = 1, be a perfect power? Erdős believed not, i.e. that Erdos672With k l holds for all k ≥ 4 and l > 1.
Denote by M(n, k) the least common multiple of the finite set n+1, dotsc, n+k. Is it true that for all m ≥ n + k, we get M(m, k) ≠ M(n, k)?
Is Σ_n=2^∞ 1/n!-1 irrational?
Is it true that, for all sufficiently large n, there exists some k such that p(n+k)>k^2+1, where p(m) denotes the least prime factor of m?
Erdős problem 681. Is it true that for all large n there exists k such that n + k is composite and p(n+k) > k^2, where p(m) is the least prime factor of m ?
Let P(n, k) be the largest prime factor of C(n, k). There exists c > 0 such that P(n, k) ≥ min(n - k + 1, k^1 + c) for all 0 < k ≤ n/2. Erdős stated this for 1 ≤ k ≤ n with the bound min(n-k+1, k^1+c) [Er79d].
Can every integer N≥2 be written as N=Π_1≤ i≤ k(m+i)/Π_1≤ i≤ k(n+i) for some k≥2 and m≥n+k?
Estimate ε_n.
Let n be sufficiently large. Is there some choice of congruence class a_p for all primes 2 ≤ p ≤ n such that every integer in [1,n] satisfies at least two of the congruences ≡ a_p (mod p)?
Let q_1 < q_2 < ⋯ be a sequence of primes such that q_i + 1 ≡ 1 pmodq_i. Is it true that lim_k → ∞ q_k^1/k = ∞?
Erdős Problem 699. Is it true that for every 1 ≤ i < j ≤ n / 2 there exists a prime p ≥ i with p | gcd(C(n, i), C(n, j))?
Is there a covering system all of whose moduli are odd (and greater than 1)?
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.
Let f(n) = min_1 < k ≤ n/2 gcd(n, C(n, k)) and let P(n) be the largest prime dividing n. (a) Characterise those composite n such that f(n) = n/P(n). Erdős–Szekeres [ErSz78] note that f(n) = n/P(n) when n is a product of two primes (erdos_700.variants.prime_mul), with n = 30 a further example.
