**Addendum**: There is a paper by Fan Chung similar to this book by Chung and Graham, Open problems of Paul Erdős in graph theory. She says there, "In November 1996, a committee of Erdős' friends decided no more such awards will be given in Erdős' name." But the same article says that Chung and Graham decided to still sponsor questions in graph theory, and this article in Science Magazine implies that they are still sponsoring the Erdős problems in general.

Some 19 years ago I collected a list of Erdős prize problems and posted them to Usenet. The problems were from "A Tribute to Paul Erdős" (1990) and "Paths, Flows, and VLSI Layout" (1980). I can repeat the problems here, although I have no idea which ones may have been solved.

$\$10000$. (T4N) **Consecutive primes are often far apart.** Conjecture: For every real number $C$, the difference between the $n$'th prime and n+1'st prime exceeds

$$C \log(n) \log(\log(n))\log(\log(\log(\log(n))))/\log(\log(\log(n)))^2$$

infinitely often. (The wording in the source does not clearly indicate that the money will be awarded if the conjecture is disproved, only if it is proved.) [**Answered**: By Kevin Ford, Ben Green, Sergei Konyagin, and Terence Tao, and independently by James Maynard, both groups in August 2014.]

$\$3000$. (T3N) **Divergence implies arithmetic progressions.** If the sum of the reciprocals of a set of positive integers is infinite, must the set contain arbitrarily long finite arithmetic progressions?

$\$1000$. (T2N) **Unavoidable sets of congruences.** A set of congruences $n = a_1 \bmod b_1$, $n = a_2 \bmod b_2$,... is unavoidable if each $n$ satisfies at least one of them. Is there an $N$ such that every unavoidable set of congruences either has two equal moduli $b_i$ and $b_j$ or some modulus $b_i$ less than $N$? [**Answered**: By Bob Hough in July 2013.]

$\$1000$. (T1C) **Three-petal sunflowers.** Is there an integer $C$ such that among $C^n$ sets with $n$ elements, there are always three whose mutual intersection is the same as each pairwise intersection? (Problem P2 is the same, except that Erdos asks about $k$-petal sunflowers for every $k$ but then says he would be satisfied with $k=3$.)

$\$500$. (T7N) **Asymptotic bases of order 2 (I).** Consider an infinite set of positive integers such that every sufficiently large integer is the sum of two members of the set. Can there be an $N$ such that no positive integer is the sum of two members of the set in more than $N$ ways?

$\$500$. (T8N) **Asymptotic bases of order 2 (II).** In the context of the previous problem, let $f(n)$ be the number of ways that n is the sum of two members of the set. Can $f(n)/\log(n)$ converge to a finite number as $n$ goes to infinity?

$\$500$. (T9N) **Evenly distributed two-colorings.** Given a black-white coloring of the positive integers, let $A(n,k)$ be the number of blacks minus the number of whites among the first $n$ multiples of $k$. Can the range of $A$ be bounded on both sides?

$\$500$. (T4C) **Friendly collections of half-sized subsets.** Given $1+(\binom{4n}{2n} - \binom{2n}{n}^2)/2$ distinct, half-sized subsets of a set with $4n$ elements, must there be two subsets which intersect only in one element? (As problem P1, 250 pounds is offered.)

$\$500$. (T1G) **Uniformity of distance in the plane (I).** Is there a real number $c$ such that n points in the plane always determine at least $cn/\sqrt{\log(n)}$ distinct distances?

$\$500$. (T1G) **Uniformity of distance in the plane (II).** Is there a real number $c$ such that given n points in the plane, no more than $n^{(1+c/\log(\log(n)))}$ pairs can be unit distance apart?

$\$500$. (P2) **Sets with distinct subset sums.** Is there a real number $c$ such that, given a set of n positive integers whose subsets all have distinct sums, the largest element is at least $c2^n$? (As in problem T1N, no prize is mentioned.)

$\$250$. (P4) **Collections of sets not represented by smaller sets.** Is there a real number $c$ such that for infinitely many positive integers $n$, there exists $cn$ or fewer sets with n elements, no two of which are disjoint, and every $(n-1)$-element set is disjoint from at least one of them?

$\$250/\$100$. (P15) **Slowly increasing Turan numbers.** If H is a (simple) graph, the Turan number $T(n,H)$ is the largest number of edges a graph with $n$ vertices can have without containing a copy of $H$. Conjecture: the function $f(n) = T(n,H)/n^{3/2}$ is bounded above if and only if every connected subgraph of $H$ has a vertex of valence 1 or 2. The larger award would be granted for a proof.

$\$100/\$25000$. (T6N) **Consecutive early primes.** An early prime is one which is less than the arithmetic mean of the prime before and the prime after. Conjecture: There are infinitely many consecutive pairs of early primes. The larger award would be granted for a disproof.

$\$100$. (T8G) **Quadrisecants in the plane.** Given an infinite sequence of points in the plane, no five of which are collinear, let $r(n)$ be the number of lines that pass through four points among the first $n$. Can it happen that $r(n)/n^2$ does not converge to zero?

issmall.) $\endgroup$ – Todd Trimble♦ May 27 '11 at 9:407more comments