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.
Asks whether n points in the plane lie on only a negligible fraction of n squared distinct unit circles containing three or more of them.
Asks whether two to the power n minus 2, plus one, points in the plane with no three collinear are always enough to force a convex n-gon.
Asks how many edge deletions make an n-vertex subgraph bipartite, and whether that number grows faster than n for graphs of uncountable chromatic number.
Determines the fewest vertices forcing every directed graph to contain an independent set of size n or a transitive tournament of size m; open, known exactly when n = 1, m <= 2, n = 2 and m <= 6, or m = 3 and n <= 5.
Asks whether the curve where a monic degree n complex polynomial has absolute value one is longest for the polynomial z to the n minus one.
Asks whether, for every infinite set of reals, some set of positive measure contains no affine copy of it.
Characterizes which number theoretic functions f make the shifted values n plus f of n cluster unboundedly in short intervals infinitely often.
Asks whether all large integers are sums of one number from each of several sets of sums of distinct powers of given bases satisfying a density condition.
Asks whether a graph on n vertices whose every induced subgraph on at least half the vertices has more than n squared over fifty edges has a triangle.
Asks how large the chromatic and clique numbers can be for the integer-distance graph on an infinite plane set with no three collinear and no four concyclic.
Asks whether any n points in the plane give two distances each occurring between at most n pairs, and whether the number of such distances grows.
Asks whether the product of k consecutive positive integers, for some k at least three, can ever be powerful, meaning every prime dividing it divides it twice.
Improves bounds on the van der Waerden number, the least N forcing a monochromatic k-term progression in any two-coloring, and whether its k-th root grows.
Asks whether, for every k at least three, there are k consecutive primes forming an arithmetic progression.
Asks for an asymptotic formula for the largest subset of the first N integers containing no non-trivial k-term arithmetic progression.
Asks whether the average of the alpha-th power of gaps between consecutive squarefree numbers up to x has a limit for every non-negative alpha.
Estimates the number of ways to write one as a sum of reciprocals of k distinct increasing positive integers.
Asks whether the strong chromatic index of any graph, the least number of induced matchings partitioning its edges, is at most five quarters of the squared maximum degree; open, with the refereed record at 1.772 times it.
Asks whether every graph on n vertices has a clique transversal of at most n minus the triangle-free independence bound H(n) vertices (Erdős–Gallai); open; best bounds n − √(2n) + √2 (explicit) and n − c√(n log n) (asymptotic).
Asks whether the mean squared gap between consecutive elements of the sumset of a finite Sidon set grows without bound as the set grows.
Asks whether the largest Sidon subset of the first N plus k integers exceeds that of the first N integers by at most one, for every fixed k and all large N.
Asks whether the first N integers contain a maximal Sidon set of size only order N to the power one third.
Asks whether every infinite integer set with at most two representations of each number as a sum of two elements has counting function whose ratio to root N has lower limit zero.
Asks whether the Ramsey number for a four-cycle versus a complete graph on n vertices is at most order n to the power two minus a fixed positive constant.
Estimates the least number of colors needed for the first N integers so that every four-term arithmetic progression receives at least three distinct colors.