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