From: greg@manifold.berkeley.edu (Greg Kuperberg)
Newsgroups: rec.puzzles,sci.math
Subject: The Erdos kitty: At least $9050 in prizes!
Date: 11 Jul 1992 01:15:17 GMT
Paul Erdos, the Hungarian problem solver extraordinaire, has offered
money for so many problems that I have decided to separate them from
the rest of my list. This posting is a partial list of Erdos prize
problems. At least $9050, and perhaps as much as $34100, in prizes,
are here for the taking!
Many of these problems were formulated jointly by Erdos and other
mathematicians. However, Erdos is the purser of all of the problems.
As I have mentioned before, the purser is the final judge and arbiter
of prize-winning solutions to each of the problems. The
award for a problem only goes to the person who solves it first,
and the purser is the arbiter of that too. I have given
my own description of each problem, but I am not responsible
for the consequences of mistakes or misleading wording in my
formulation.
If you are getting somewhere one of the problems, or if you plan
to try, you can contact me at greg@math.berkeley.edu. Please
contact me if you know of other Erdos prize porblems.
The problems listed here are from two sources:
T = A Tribute to Paul Erdos, Cambridge University Press, 1990, pp. 467-477.
P = Paths, Flows, and VLSI Layout, Springer-Verlag, 1980, pp. 35-45
The problems are labeled by their source and number in the reference.
In addition, problems in the first reference are labeled by topic:
N = Number theory
C = Combinatorics and graph theory
G = Geometry
----------------------------------------------------------------------------
$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.)
$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 mod b_1, n = a_2 mod 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?
$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+((4n choose 2n) - (2n choose 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^k? (As 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?
==============================================================================
Newsgroups: rec.puzzles,sci.math
From: bs@faron.mitre.org (Robert D. Silverman)
Subject: Re: The Erdos kitty: At least $9050 in prizes!
Date: Sat, 11 Jul 1992 01:49:43 GMT
In article <13lcn5INN7hn@agate.berkeley.edu> greg@manifold.berkeley.edu (Greg Kuperberg) writes:
:Paul Erdos, the Hungarian problem solver extraordinaire, has offered
:
stuff deleted....
:$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
This is not a conjecture. It is a THEOREM due to Rankin, with C = exp(gamma).
Erdos offers $10K for showing that the constant C can be taken arbitrarily
large.
Note: Carl Pomerance has slightly improved the constant C.
:
: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.)
Either the source is wrong, or you misinterpreted it.
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"
==============================================================================
From: asari@math.uiuc.edu (ASARI Hirotsugu)
Newsgroups: sci.math.research,sci.math
Re: Erdos problems
Date: Mon Jan 04 22:55:18 CST 1999
In article <3690994C.41C6@see.signature.for.address>, James Annan
wrote:
> Does anyone know of an on-line list of Erdos' conjectures and unsolved
> problems? My web surfing has only found things like the Erdos number
> project page...
>
> Thanks,
>
> James
If you are looking for Graph theory problems, Fan Chung has made it
available on the web:
--
ASARI Hirotsugu // http://www.math.uiuc.edu/~asari/
Graduate Student/Teaching Assistant // mailto:asari@member.ams.org
==============================================================================
From: John Scholes
Newsgroups: sci.math.research,sci.math
Re: Erdos problems
Date: Wed Jan 06 01:03:24 CST 1999
James Annan writes
>Does anyone know of an on-line list of Erdos' conjectures and unsolved
>problems? My web surfing has only found things like the Erdos number
>project page...
Others have mentioned various web pages. You should also look at:
Erdos on graphs, his legacy of unsolved problems, Fan Chung & Ron
Graham, AK Peters 1998. $30 from Amazon.
I find much of the research literature on graph theory is bedevilled by
being far harder to read than it need be. This book is an exception. It
is still far from an easy read, but it does set out the problems
clearly, with some commentary, introduction and motivation. Obviously it
also has references. Worth looking at. Of course, it only covers the
graph related problems.
--
John Scholes