Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
516 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Studies the least greatest common divisor of n and n choose k over k between 1 and half of n, asking when it is large and how big it can be for composite n.
Estimates the chromatic number of the unit distance graph in n-dimensional space, whose edges join points at distance exactly one.
Bounds the largest chromatic number of a graph on finitely many plane points whose edges join pairs at one of r prescribed distances.
Bounds the fewest integers from a run of consecutive integers whose product is divisible by the product of n given integers; the corrected at-most statement is open, with a partial bound of 12n pending.
The least multiplier f(n) such that any f(n) max(A) consecutive integers hold distinct multiples of the n members of A, for every n-set A; known to lie between log n over log log n and root n, with a formula asked for.
Bounds the shortest interval anywhere holding distinct integers, the kth divisible by k, for k up to n, against the one just above n; the comparison is proved (van Doorn 2026), the n to the 1+o(1) bound open, n^(3/2) proved.
Asks for the Turán density of the complete r-uniform hypergraph on k vertices for any k > r > 2; Turán's 1941 theorem settles r = 2 and no pair with r > 2 is known, with Erdős's two prize offers standing.
Asks whether every bipartite graph with at least two edges has extremal number asymptotic to a constant times a power of n in [1, 2), and whether that power is rational; Erdős's 1967 exponent shapes were disproved in 1970.
Asks whether the largest graph on n vertices with no complete bipartite subgraph with r vertices per side has roughly n to the power 2 minus one over r edges.
Asks whether every r-uniform hypergraph on n vertices is a union of at most ex_r(n; K_{r+1}^r) edges and (r+1)-cliques, no two sharing an edge; the Erdős–Sauer conjecture, known for r = 2.
Asks whether the order of a finite projective plane must always be a power of a prime.
Asks whether the largest number of mutually orthogonal Latin squares of order n grows at least as fast as a constant times the square root of n.
Asks for an asymptotic formula for the number of Latin rectangles with k rows and n columns.
Asks whether the sum of one over p, over primes p at most n whose remainder of n lies in the upper half of the interval up to p, is about half of log log n.
Asks, for each k at least 2, whether the square of the factorial of n plus k divides the factorial of two n for infinitely many n.
Asks for a non-trivial pairwise balanced design on n points in which each block size is used at most about the square root of n times.
Asks whether a graph of chromatic number aleph one must, for every cardinal m, admit a graph of chromatic number m all of whose finite subgraphs occur in it.
Asks whether every triangle-free graph of infinite chromatic number contains every tree as an induced subgraph.
Asks whether a graph of infinite chromatic number m must have a subgraph of chromatic number n for every infinite cardinal n below m.
Asks whether the complete graph on n vertices can always be split into edge-disjoint copies of given trees with 2, 3, up to n vertices; the tree packing conjecture of Gyárfás, open, with one arXiv proof claim withdrawn.
Asks whether a set of naturals can have a sumset of lower density near one while every integer has boundedly many representations as a sum of two elements.
Determines the best constant c such that n reals whose every four-element subset has at least eleven differences contain a Sidon set of size c times n.
Asks how the least number of colors whose classes induce complete or empty graphs compares with the least number avoiding monochromatic oriented cycles.
Asks for estimates of the least Turán number over all graphs with k vertices and l edges in the range k < l ≤ k²/4, and whether it is strictly monotone in l; open, with asymptotics known at the pairs (5,6) and (6,9) only.
Bounds the least k beyond which the n-dimensional unit cube splits into k homothetic cubes, in particular whether it grows at least like n to the power n.