Some of Paul's favorite problems (1999)

../

problem_1_22: Records the 1999 booklet's item 1.22, which asks for the largest subset B of a set A of n integers avoiding, in turn, b_1 + b_2 = b_3 in B, an element of B equal to a sum of distinct others in B, b_1 + b_2 equal to an element of A, and coinciding subset sums, with the estimates the booklet records.

problem_2_44: Records the exact 1999 formulation of the ordinary-Lagrange local question.

problem_6_76: Records the original random-radius definition and exponential-law conjecture.

problem_6_77: Records the original infinitely-often question about ties for maximum local time.

problem_6_78: Records the almost-sure polylogarithmic conjecture for all past favorite sites.

---

Some of Paul's favorite problems, booklet circulated at the conference Paul Erdős and his mathematics, Budapest, July 1999. The final printed page credits a collection by B. Bollobás, Z. Füredi, A. Hajnal, G. Halász, G. O. H. Katona, P. Komjáth, M. Laczkovich, L. Lovász, L. Pyber, P. Révész, I. Z. Ruzsa, A. Sárközy, M. Simonovits, V. T. Sós, J. Szabados, T. Szőnyi, K. Vesztergombi, and P. Vértesi.

Canonical source. The nine-spread scan is hosted by Vjekoslav Kovač at the University of Zagreb. The file includes handwritten introductory material and paired printed pages; PDF page numbers therefore differ from printed ones. The scan has cropped letters at some outer edges. Selected formulas were read visually; an unverified transcription is not the canonical source. No notice is printed on the scan's rendered first or last page, and the hosting directory it was taken from is a bare file listing with no terms (https://web.math.pmf.unizg.hr/~vjekovac/EP/); the booklet identifies no publisher, its last page crediting only the collectors; the term is unstated.

This is the booklet cited as [Va99] on erdosproblems.com. It is a historical collection, so its conjectures and solution notices describe its own period. It covers number theory, analysis, graphs and hypergraphs, geometry, algebra, probability, and set theory. Its primary filing is a single broad home; verified problem relationships supply the cross-references to other subjects.

Selected original statements

PDF p. 5, right leaf, item 2.44 prints the ordinary-Lagrange local question corresponding to Problem 1153. Its setup is item 2.40 on the left leaf of the same spread, with distinct nodes and $\lambda(X_n,x)=\sum_k|l_k(X_n,x)|$. The item 2.44 statement record preserves the printed $[2/\pi+o(1)]\log n$ convention and its relationship to the modern $-o(1)$ form. This is an exact historical statement, not current status evidence.

Printed p. 12, the left half of PDF p. 8, gives:

• Problem 6.76: the random radius of the disc centered at the origin covered by a planar walk, its expected scale, and Kesten's proposed exponential limit law.
• Problem 6.77: probabilities of infinitely many occurrences of exactly $r$ favorite sites.
• Problem 6.78: a polylogarithmic bound on the union of all earlier favorite sets.

The setup starts on printed p. 11, the right half of PDF p. 7. These are statement records, not proofs. In particular, Problem 6.76 defines a path-dependent radius and prints a cumulative distribution of the form $1-e^{-\lambda x}$; it does not place an almost-every-walk quantifier inside a deterministic finite-time radius definition.

PDF p. 6, left leaf (read on the page image; the printed page number is not legible on the render), in the Ramsey section, prints the sentence "Erdős and Szekeres proved that $cn2^{n/2}<R(n)\le\binom{2n-2}{n-1}$" (the lower bound is Erdős's 1947 probabilistic bound, folded here into the attribution) followed by item 3.49, "Find a constructive proof of $R(n)>(1+c)^n$", the booklet's form of Problem 78, and item 3.50, "Prove that $\lim_{n\to\infty}R(n)^{1/n}=c$ exists", the booklet's form of Problem 77 (existence only; the site's question asks for the value), and item 3.51, "Prove $r(4,n)>n^{3-\varepsilon}$", the booklet's form of Problem 166 (without the logarithmic factor of the site's statement; the booklet writes $r(4,n)$ here and $R(n)$ in 3.49 and 3.50). The same leaf prints item 3.54, "(Erdős, Faudree, Ordman) Let $f(n)$ be the smallest integer for which if we color the edges of $K(n)$ by two colors there are at least $f(n)$ edge disjoint monochromatic triangles. Is it true that $f(n)=(1+o(1))\frac{n^2}{12}$?", the booklet's form of Problem 76 (the site cites "Va99, 3.54"; the booklet's $f(n)$ is Erdős's 1995 $h(n)$). All four are historical statements read clause by clause on the page image; no result page was made for them. Read status: claims checked for items 3.49, 3.50, 3.51 and 3.54 (PDF p. 6, left leaf), read on the page image.

PDF p. 7, left leaf (read on the page image; its printed page number is not legible on the render, and the right leaf of the same spread is printed p. 11), Section 3.5 "Set-systems", prints item 3.64, "Find the maximum number of edges in a $t$-uniform hypergraph in which every $k$ vertices span at most $r$ edges. This very difficult question contains the existence problem of block designs, the Ruzsa--Szemerédi Theorem etc.", the booklet's form of Problem 1157, and item 3.65, "Find a matching lower bound for the hypergraph version of the Kővári--T. Sós--Turán Theorem. Let $\mathrm{ex}_t(n,r)$ denote the maximum number of edges in a $t$-partite $t$-uniform hypergraph that does not contain a complete $t$-partite subhypergraph with $r$ vertices in each class. What is $\lim_{n\to\infty}\log\mathrm{ex}_t(n,r)/\log n$? Is the 1962 bound $t-\frac1{r^{t-1}}$ of Erdős best possible?", the booklet's form of Problem 1158 (the booklet's letters $t$ and $r$ are the site's). Both are historical statements read clause by clause on the page image; no result page was made for them. Read status: claims checked for items 3.64 and 3.65 (PDF p. 7, left leaf), read on the page image.

PDF p. 3 (read on the page image; the left leaf is printed p. 2, its page number legible at the foot, and the right leaf printed p. 3), Section 1.2 "Egyptian fractions", prints item 1.13, "(Erdős, Straus) Prove that for every $n>1$ $\frac4n=\frac1x+\frac1y+\frac1z$ is solvable in integers $x,y,z$" (the display closes the left leaf and the words "is solvable in integers $x,y,z$" open the right leaf), the booklet's form of Problem 242 (the site asks for $n>2$ and distinct $x<y<z$; the booklet asks for $n>1$ and prints no distinctness); item 1.14, "What is the maximum number of integers $a_1<a_2<\dots<a_k\le n$ [such] that no sum $\sum\frac{\epsilon_i}{a_i}$, ($\epsilon_i=0,1$) equals 1? Can $k$ be $n-o(n)$?" (the word before "that" is cut at the scan's right edge), the booklet's form of Problem 300; and item 1.15, "If $a_1<a_2<\dots<a_n$ are positive integers and $\sum\frac1{a_i}=1$, then $\max_i(a_{i+1}-a_i)>2$", the booklet's form of Problem 287 (the item is printed as an assertion, its word "then" cut at the scan's right edge after "th"; a strict inequality $>2$ between integers is the site's $\ge3$; the booklet prints no $a_1>1$). Read status: claims checked for items 1.13, 1.14 and 1.15, read clause by clause on the page image.

PDF pp. 3--4 (read on the page images; the right leaf of PDF p. 3 is printed p. 3 and the left leaf of PDF p. 4 is printed p. 4 by the order of the spreads, its number not legible on the render), Section 1.3 "Additive number theory", prints item 1.22, "We have a set $A$ of $n$ integers and we want to select a subset $B\subset A$, $|B|=k$ as large as possible, with certain properties. The question is to estimate the maximal $k$", with four parts: a) "Avoid $b_1+b_2=b_3$ with $b_i\in B$. The maximum of $k$ is somewhere between $n/3$ and $n/2$", the booklet's form of Problem 792; b) "Avoid $b_2=b_2+b_3+\dots+b_m$ [so printed; the first symbol is evidently $b_1$] for any number of distinct $b_i\in B$. Is $k>cn$ always possible?", the booklet's form of Problem 790 (asked as a linear-size question, which the 1975 bound $l(n)\ll n/\log n$ of Choi, Komlós and Szemerédi answers in the negative); c) "Avoid $b_1+b_2=a$, $b_i\in B$, $a\in A$. No decent estimates", the booklet's form of Problem 787; and d) "Find $B$ so that all $2^k$ subset sums are distinct. Maximum is between $\log_3n$ and $\log_2n$", the booklet's form of Problem 963 (the distinct-subset-sums question of the 1965 paper, p. 188). The right edge of the item's opening lines is cropped after "$B\subset A$". The item is on problem_1_22. Read status: claims checked for item 1.22 (PDF pp. 3--4), read clause by clause on the page images on 2026-09-18; a 1999 statement that proves nothing.

The remaining entries have not been systematically mapped to the modern problem numbers or checked against later literature. No complete extraction of the booklet is claimed.

Bears on. #1153, #1164, #1165, #1166, #77 (item 3.50, PDF p. 6, left leaf), #78 (item 3.49, PDF p. 6, left leaf), #166 (item 3.51, PDF p. 6, left leaf), #76 (item 3.54, PDF p. 6, left leaf: the least number $f(n)$ of edge-disjoint monochromatic triangles forced in every two-coloring of $K(n)$, asked to be $(1+o(1))n^2/12$), #1157 (item 3.64, PDF p. 7, left leaf, Section 3.5: the maximum number of edges of a $t$-uniform hypergraph in which no $k$ vertices carry more than $r$ edges, which the booklet says contains the existence of block designs and the Ruzsa--Szemerédi theorem), #1158 (item 3.65, PDF p. 7, left leaf, Section 3.5: $\lim_{n\to\infty}\log\mathrm{ex}_t(n,r)/\log n$ for $t$-partite $t$-uniform hypergraphs with no complete $t$-partite subhypergraph having $r$ vertices per class, and whether Erdős's 1962 bound $t-1/r^{t-1}$ is sharp), #242 (item 1.13, PDF p. 3, printed pp. 2--3: the Erdős--Straus equation for every $n>1$), #300 (item 1.14, PDF p. 3, printed p. 3: the maximum number of $a_i\le n$ with no subset of reciprocals summing to $1$, and whether it can be $n-o(n)$) and #287 (item 1.15, PDF p. 3, printed p. 3: $\sum1/a_i=1$ forces a consecutive gap $>2$), #963 (item 1.22 d), PDF pp. 3--4: select $B$ whose $2^k$ subset sums are all distinct, with the maximum $k$ placed between $\log_3n$ and $\log_2n$), #787 (item 1.22 c), PDF pp. 3--4: avoid $b_1+b_2=a$ with $b_i\in B$, $a\in A$, for which the booklet records no decent estimate), #790 (item 1.22 b), PDF pp. 3--4: avoid $b_1=b_2+\dots+b_m$ for distinct $b_i\in B$, asking whether $k>cn$ is always possible) and #792 (item 1.22 a), PDF pp. 3--4: avoid $b_1+b_2=b_3$ in $B$, with the maximum $k$ placed between $n/3$ and $n/2$); and, from Section 7 "Set theory" (PDF p. 8, right leaf, printed p. 13, except item 7.94 on PDF p. 9, left leaf, printed p. 14), #1171 (item 7.84), #1169 (item 7.85), #1174 (item 7.91), #1176 (item 7.93) and #1177 (item 7.94).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.