Erdos 1982 my favourite problems which recently have

../

---

P. Erdős: Some of my favourite problems which recently have been solved, Proceedings of the International Mathematical Conference, Singapore 1981 (Singapore, 1981), North-Holland Math. Stud., 74 , pp. 59--79, North-Holland, Amsterdam-New York, 1982 MR 84f:10003; doi:10.1016/S0304-0208(08)70415-8 (Crossref record read).

The copy read for this card is a 21-page OmniPage scan of the article (printed p. n is PDF p. n − 58) whose OCR text layer garbles the formulas; the two passages recorded below for Problems 720 and 911 were read on the page images of PDF pp. 12, 13 and 20 (printed pp. 70, 71 and 78). The scan prints "©North-Holland Publishing Company, 1982" at the head of its first page, every other right reserved.

Read status: claims checked for the size Ramsey passage of Section 3 (p. 70), the two "last minute" problems of p. 78 and, read on the page image, the weighted-clique passage of p. 78 (display (3), the definition (4) of F(n), Rödl's bounds and the three-color remark), the Burr--Erdős conjecture (1) of p. 78 re-read clause by clause on the page image for Problem 163, the Hamiltonian random-graph passage of Chapter III, §1 (printed p. 69 = PDF p. 11) and the de Mathan--Pollington passage of Chapter II, §1 (printed p. 63 = PDF p. 5), both read clause by clause on the page images, and the distances-near-integers passage of Chapter II, §9 (printed pp. 67--68 = PDF pp. 9--10), read clause by clause on the page images for Problems 465, 466 and 953, and the Bollobás--Erdős triangle passage of Chapter III, §5 (printed p. 71 = PDF p. 13), read clause by clause on the page image for Problems 80, 905 and 1033, the longest-path passage of §1 (printed p. 69 = PDF p. 11) and the Schütte passage of §2 (printed p. 70 = PDF p. 12), both read clause by clause on the page images for Problems 900 and 902, and the §5 passage of p. 71 re-read on the page image for Problem 1034; the statements of the other items are unread; the paper proves nothing, so there is no proof to check.

A wide-ranging survey without new proofs, organized into five chapters, each item stating a conjecture and who settled it. Chapter I on geometry recalls the Erdős-Mordell inequality PA + PB + PC ≥ 2(PM + PN + PL), conjectured by Erdős in 1932 and proved by Mordell in 1934 (section 1, p. 61); the Erdős-Szekeres convex polygon problem with 2^{n-2} + 1 ≤ f(n) ≤ binom(2n-4, n-2); and the unit-distance problem, where Erdős proved n^{1 + c_1/log log n} < f(n) < c_2 n^{3/2}, conjectured the lower bound is the right order, notes Szemerédi and Józsa proved f(n)/n^{3/2} → 0, and offers a prize for a proof or disproof (section 3, pp. 61-62). Chapter II on number theory covers prime gaps and Maier's theorem, Sidon B_2 sequences with a_k = o(k^3) proved by Ajtai, Komlós and Szemerédi, Halász and Wirsing on multiplicative functions, and in section 6 (pp. 66-67) the divisor functions: Erdős notes that he and Tenenbaum recently disproved his conjecture tau^+(n)/tau(n) → 0 for almost all n, and states the problem of proving Q(n) = sum d_i/d_{i+1} → infinity for almost all n, remarking, as printed, that it is trivial that Q(n) → infinity for almost all n, and reporting that he and Tenenbaum proved in July 1981 that Q(n)/tau(n) has a continuous distribution function. Chapter III on combinatorics records in section 5 (p. 71) the Burr-Erdős conjecture that for odd k every graph G(n; [c_k n]) has, for every residue ℓ, a cycle of length congruent to ℓ mod k, proved by Bollobás with c_k = k(k+1)2^k, and the Bollobás-Erdős conjecture that every G(n;m) with m > n^2/4 has a triangle with degree sum v(x_1)+v(x_2)+v(x_3) ≥ 3n/2, which Erdős reports Edwards proved, adding that Edwards proved the more general conjecture, with k(r) in place of k(3), nearly in its full generality; as printed, the bound 3n/2 is inconsistent with Problem 1033's upper bound. Chapter IV section 1 (p. 72) states the two entire-function problems from Erdős's 1956 Hungarian paper, including whether there is an entire f such that, for every infinite sequence n_1 < n_2 < ..., the roots of the derivatives f^{(n_i)} together are everywhere dense, reporting that both functions had been shown to exist over a decade before. Chapter V section 2 (p. 76) is the Erdős-Hajnal-Milner question for a limit ordinal alpha, whether every graph on alpha contains an infinite path or an independent set of order type alpha, proved for all alpha < omega_1^{omega+2} with prizes offered for omega_1^{omega+2} and for the general case. These items are respectively the paper's bearing on Problems 898, 90, 673, 71, 1033, 906 and 601.

Two further passages, read on the page images. Section 3 of Chapter III (printed p. 70, PDF p. 12) states the size Ramsey problem of Problem 720 as settled. It attributes the problem to Faudree, Rousseau, Schelp and Erdős, says it "has recently been settled by J. Beck", and defines the size Ramsey number r̂(G_1,G_2) as the least number of edges of a graph G with G → (G_1,G_2), that is, every two-coloring of the edges of G gives a copy of G_1 in the first color or of G_2 in the second. Then: "We asked for a determination or estimation of r̂(P_n,P_n) and r̂(C_n,C_n). We expected that (P_n is a path of length n and C_n a cycle of n edges.) r̂(P_n,P_n)/n → ∞ but r̂(C_n,C_n)/n² → 0. J. Beck in fact proved: (1) r̂(P_n,P_n) < C_1 n, r̂(C_n,C_n) < C_2 n." The passage adds that the best constants in (1) are not known and that Beck proved extensions of (1) to trees, and, at the top of p. 71, "The results of Beck have not yet been published." The closing page (printed p. 78, PDF p. 20) adds two "last minute" problems from a meeting in Eger: first, the question of Problem 911, "Let G(n;e) be a graph of n vertices and e edges. We assume that e/n is large. Is it true that there is a function f(x), f(x)/x → ∞ as x → ∞ for which r̂(G(n;e)) > e f(e/n)?"; second, for graphs G(n) all of whose k-vertex subgraphs have fewer than ck edges, the Burr-Erdős conjecture (1) r̂(G(n)) < f(c)n (printed with the hat of the size Ramsey number, a misprint the next sentence, "the ordinary diagonal Ramsey number of G(n) is less than Cn", corrects) and its size-Ramsey strengthening (2) r̂(G(n)) < f(c)n, "my first feeling would be to try to find a counter example to (2)". The page ends with the weighted-clique conjecture and Rödl's proof of it: "Several years ago I conjectured that if one colours the edges (i,j), 1 ≤ i < j ≤ n, by two colours, then if t is any given number and n > n_0(t) then there is always a monochromatic complete graph having the vertices 1 ≤ i_1 < ... < i_k ≤ n for which (3) Σ_{r=1}^k 1/(1 + log i_r) > t. The interest of (3) is that it does not follow immediately from Ramsey's theorem. Rödl now proved (3)." Display (4) defines F(G(n)) as the largest such sum over the monochromatic complete graphs of a coloring and F(n) as its minimum over all colorings, and "Rödl proved that c_1 log log log log n / log log log log log n < F(n) < c_2 log log log n. He also showed that (3) fails for colouring with three colours. His paper on this subject will appear soon."

Source: https://users.renyi.hu/~p_erdos/1982-33.pdf.

Bears on. #71, #90, #601, #673, #720: Section 3, printed p. 70, restates the path question, adds the cycle expectation and credits Beck with both linear bounds, then unpublished; #898, #906, #911: the first "last minute" problem of printed p. 78 is the problem's statement in its original source; #559: the second "last minute" problem of printed p. 78 (PDF p. 20, page image), display (2) $\hat r(G(n))<f(c)n$ for graphs all of whose $k$-vertex subgraphs have fewer than $ck$ edges, is a size-Ramsey conjecture stronger than the problem's bounded-degree statement (a graph of maximum degree $d$ has fewer than $dk$ edges on any $k$ vertices), stated as "Perhaps in fact" and doubted in the sentence quoted above; a passage for the attribution question on the problem page; #191: the closing passage of printed p. 78 (PDF p. 20, page image), the conjecture (3) with the weight 1/(1 + log i_r), the report that Rödl proved it with the bounds on F(n) in display (4) and that it fails for three colors, and "His paper on this subject will appear soon" (the paper appeared in 2003); #905: Chapter III, §5, printed p. 71 (PDF p. 13, page image), the site's source key Er82e: "Bollobás and I conjectured that every $G(n;[\frac{n^2}4]+1)$ has an edge which is contained in at least $\frac n6$ triangles, and we observed that, if this is true, it is best possible. For the proof we needed the following further conjecture: Let $m>\frac{n^2}4$. Then every $G(n;m)$ contains a triangle $(x_1,x_2,x_3)$ for which (1) $v(x_1)+v(x_2)+v(x_3)\ge\frac{3n}2$, where $v(x)$ is the valency or degree of $x$. In fact we formulated a more general conjecture (for $k(r)$ instead of $k(3)$). Edwards proved (1) and he in fact proved our conjecture nearly in its full generality.", followed by the reference "C. S. Edwards, Complete subgraphs with largest sum of vertex degrees, Coll. Math. Soc. J. Bolyai 18, Combinatorics, Edited by A. Hajnal V. T. Sós, North Holland 1978, 293."; the $n/6$ problem is attested only through the conjecture (1) its proof "needed", reported proved by Edwards, and (1) as printed is inconsistent with Problem 1033's upper bound, as the problem page records; #1033: the same passage of Chapter III, §5, printed p. 71 (PDF p. 13, page image), the "further conjecture" (1) that every $G(n;m)$ with $m>n^2/4$ contains a triangle with $v(x_1)+v(x_2)+v(x_3)\ge3n/2$, the site's "In [Er82e] it is asked whether $h(n)\ge\frac32n$", with "Edwards proved (1)" and the Edwards reference; the display prints $\ge$, and the problem page records that (1) as printed is inconsistent with the upper bound $h(n)\le2(\sqrt3-1)n+O(1)$; #163: the second "last minute" problem of printed p. 78 (PDF p. 20, page image), display (1): "Let G(n) be a graph with bounded edge density for all subgraphs. In other words there is an absolute constant c so that if G(k) is any subgraph of G of k vertices then the number of edges of G(k) is less than ck. Burr and I conjectured several years ago that then (1) r̂(G(n)) < f(c)n. In other words the ordinary diagonal Ramsey number of G(n) is less than Cn where C depends only on c." The display prints the hat of the size Ramsey number, a misprint the next sentence corrects; this is the Burr--Erdős conjecture of 1975 in its edge-density form (fewer than ck edges on any k vertices), the site's source key Er82e for the problem, stated as open in 1982 and proved by Lee (arXiv preprint 2015, Ann. of Math. 2017); the size-Ramsey strengthening (2) that follows is Problem 559's passage; #746: Chapter III, §1, printed p. 69 (PDF p. 11, page image), second paragraph: "Rényi and I conjectured that with probability tending to one every G(n;[(1/2 + ε)n log n]) is Hamiltonian. This conjecture was proved by Pósa in a very ingenious way with c n log n instead of (1/2 + ε)n log n. ... The full conjecture was proved soon afterwards by Kurshonov and Komlós-Szemerédi." (the spelling "Kurshonov" is the print's), followed on the same page by the references to Pósa, Hamiltonian cycles in random graphs, Discrete Math. 14 (1976), 359-364, and Komlós and Szemerédi, Limit distribution for the existence of Hamilton cycles in random graphs, "to appear in Discrete Mathematics"; #464: Chapter II, §1, printed p. 63 (PDF p. 5, page image): "Here I only restate one of the problems which has been settled since then by de Mathan and Pollington (independently): Let n_1 < n_2 < ... satisfy n_{k+1}/n_k > c > 1. Then there is always an irrational α for which the fractional part of n_k α is not everywhere dense. It turned out that the set of these α's has Hausdorff dimension 1 in every interval.", followed on the same page by the references "P. Erdös, Problems and results on diophantine approximations I and II, Compositio Math. 16 (1964), 52-65 and Répartition Modulo 1, Coll. Masseille-Luminy [sic] 1974, Lectures [sic] notes in math. 475, Edité par G. Rauzy, 89-97", "G. Wagner, Problem of Erdös in Diophantine approximation, Bull. London Math. Soc. 12 (1980), 81-88", "B. de Mathan, Number contravening a condition in density modulo 1, Acta Math. Acad. Sci. Hungar. 36 (1980), 237-241" and "A. D. Pollington, On the density of sequence {n_k ξ}, Illinois J. Math. 23 (1979), 511-515" (titles as printed); the site's source key Er82e for the problem, Erdős's own announcement of the solution in the "not everywhere dense" form, and the passage that identifies the site's key Er75i with the second of the two Erdős papers named here, the Répartition Modulo 1 chapter (pp. 89-97 of Lecture Notes in Math. 475); #465 and #466: Chapter II, §9, printed pp. 67--68 (PDF pp. 9--10, page images), the site's source key Er82e for both problems: "Denote by $N(x,\delta)$ the maximum number of points $p_1,\ldots,p_n$ which can be chosen in a circle of radius $x$ so that the distance between any two of them differs by at least $\delta$ from every integer. I conjectured that $N(x,\delta)=o(x)$ and $N(x,\delta)\to\infty$. The first conjecture was proved by Sárközy who proved $N(x,\delta)<cx/(\delta^3\log\log x)$. Graham proved the second conjecture, he in fact proved $N(x,1/10)>\frac1{10}\log x$. Sárközy showed that to every $\varepsilon>0$ there is a $\delta(\varepsilon)>0$ so that for every $\delta<\delta(\varepsilon)$ $N(x,\delta)>x^{1/2-\varepsilon}$. Perhaps for every $\varepsilon>0$ $N(x,\delta)<x^{1/2+\varepsilon}$", followed by the reference "Sárközy, On distances near integers I and II, Studia Sci. Math. Hungar. 11 (1976), 37-50 and 105-111"; the passage writes the radius as a lowercase $x$ throughout, and its two conjectures are Problem 465's first question and Problem 466's question, with the closing "Perhaps" Problem 465's second question; #953: Chapter II, §9, printed pp. 67--68 (PDF pp. 9--10, page images), the passage quoted above for Problems 465 and 466: it poses the point-count form, the maximum number $N(x,\delta)$ of points in a circle of radius $x$ whose pairwise distances differ from every integer by at least $\delta$, with the Sárközy and Graham bounds, and does not state the problem's measure question (the largest measure of a measurable set in a disc of radius $r$ with no two points at an integer distance); the site's pages for Problems 465 and 466 point to Problem 953 as "a similar problem"; #80: Chapter III, §5, printed p. 71 (PDF p. 13, page image), the Bollobás--Erdős passage quoted under Problem 905: the conjecture that every $G(n;[\frac{n^2}4]+1)$ has an edge in at least $\frac n6$ triangles is the problem's function at every density above one quarter ($f_c(n)\ge n/6$ for $c>1/4$, the bound the problem page records from Edwards and from Khadzhiivanov and Nikiforov), and the closing sentence quoted under Problem 905, Edwards's proof of (1) and of the conjecture nearly in full generality, is Erdős's own report of Edwards's proof, the site's "Edwards (unpublished)"; the passage says nothing about densities below one quarter or about the hypothesis that every edge lies in a triangle, and the more general conjecture it mentions, with $k(r)$ in place of $k(3)$, generalizes the degree-sum conjecture (1) to complete $r$-graphs, not the book problem; #900: the site's key Er82e; §1, printed p. 69 (PDF p. 11, page image), the first paragraph, before the Hamiltonian passage quoted for Problem 746: "§1. I conjectured that for every $\frac12<c<\infty$ there is a function $f(c)$ so that every random graph $G(n;cn)$ contains a path of length at least $f(c)n$ where $f(c)\to0$ as $c\to\frac12$ and $f(c)\to1$ as $c\to\infty$. All these conjectures were proved by Ajtai, Komlós and Szemerédi", followed on the same page by the reference "M. Ajtai, J. Komlós and E. Szemerédi, The longest path in a random graph, Combinatorica 1 (1981), 1-12"; the problem's statement in Erdős's own words, in the form the site uses, with his report of its proof; #902: the site's key Er82e; §2, printed p. 70 (PDF p. 12, page image), after the property B passage: "Schütte asked me 20 years ago, is there for every $n$ an $f(n)$ so that there is a tournament (or a complete directed graph) of $f(n)$ players so that every set of $n$ players is beaten by at least one of the players. Schütte observed $f(1)=3$, $f(2)=7$ but it seemed difficult to calculate $f(n)$ for $n>2$ (or even to prove the existence of $f(n)$). I proved by the probability method that for some $c>0$ (3) $2^{n+1}-1\le f(n)\le cn^22^n$, and I asked for an improvement of (3). E. and G. Szekeres proved $f(3)=19$ and $f(n)>cn2^n$. At the moment an asymptotic formula for $f(n)$ seems beyond reach", followed on the same page by the references "P. Erdös, On a problem in graph theory, Math. Gazette, 47(1963), 220-223" and "E. Szekeres and G. Szekeres, On a problem of Schütte and Erdös, Math. Gazette, 49(1975), 290-293" (the print's "1975" for the 1965 volume); Erdős's own statement of the problem with the bounds of his 1963 paper and his attestation of the two Szekeres results; #1034: Chapter III, §5, printed p. 71 (PDF p. 13, page image), the Bollobás--Erdős passage quoted under Problem 905, re-read: it states the conjecture that every $G(n;[\frac{n^2}4]+1)$ has an edge in at least $\frac n6$ triangles, the degree-sum conjecture (1) and Edwards's proof of it; it does not state the problem's stronger question (a triangle with more than $(\frac12-o(1))n$ vertices each joined to two of its vertices), which the site attributes to Erdős and Faudree in a 1993 collection, so the passage is the 1982 statement of the weaker problem of which the site calls Problem 1034 "a stronger version"; #702: Chapter III, §6, printed p. 72, the conjecture of Sós and Erdős, after their observation that at most $n$ triples of an $n$-set have no two meeting in exactly one point, with equality if and only if $n\equiv0\pmod4$: "We further conjectured that if $|S|=n$, $A_i\subset S$, $1\le i\le t_k$, $|A_i|=k$ and $|A_i\cap A_j|\ne1$ for every $1\le i<j\le k$ [sic] then for $n>n_0(k)$ (1) $\mathrm{Max}\,t_k=\binom{n-2}{k-2}$. (1) was proved for $k=4$ by Katona and by P. Frankl in the general case.", followed by the reference to Frankl's paper in Bull. Austral. Math. Soc. 17 (1977); the misprinted upper index $k$ in $j\le k$ stands for $t_k$; the statement carries the range $n>n_0(k)$ that the site's wording omits, and reports Frankl's proof, the site's source key Er82e for the problem.

Results to transcribe.

• Section I.1, p. 61: Erdős-Mordell inequality: for a point P inside triangle ABC, PA + PB + PC ≥ 2(PX + PY + PZ) for the feet of the perpendiculars; conjectured by Erdős in 1932 and proved by Mordell in 1934.
• Section I.3, pp. 61-62: For the largest number f(n) of unit distances among n points in the plane, Erdős proved n^{1+c_1/log log n} < f(n) < c_2 n^{3/2}, conjectured the lower bound is the correct order, and offers a prize for a proof or disproof; Szemerédi and Józsa proved f(n)/n^{3/2} → 0.
• Section II.6, pp. 66-67: Erdős reports that he and Tenenbaum disproved his conjecture that tau^+(n)/tau(n) → 0 for almost all n, states the problem of proving Q(n) = sum d_i/d_{i+1} → infinity for almost all n (calling the same statement trivial a few lines later, as printed), and reports that he and Tenenbaum proved Q(n)/tau(n) has a continuous distribution function.
• Section III.5, p. 71: Burr-Erdős conjecture that for odd k every graph G(n; [c_k n]) contains, for every residue ℓ, a cycle of length ≡ ℓ mod k was proved by Bollobás with c_k = k(k+1)2^k; Erdős expected the optimal c_k to be far smaller.
• Section III.5 (1), p. 71: Bollobás-Erdős conjecture that every G(n;m) with m

  n^2/4 contains a triangle x_1,x_2,x_3 with v(x_1)+v(x_2)+v(x_3) ≥ 3n/2, reported proved by Edwards, who "in fact proved our conjecture nearly in its full generality" (the k(r) form); as printed, (1) is inconsistent with Problem 1033's upper bound.

• Section V.2, p. 76: For a limit ordinal alpha, does every graph on vertex set of type alpha contain an infinite path or an independent set of type alpha? Erdős, Hajnal and Milner proved it for all alpha < omega_1^{omega+2}; prizes offered for omega_1^{omega+2} and for the general case.
• Section III.3, p. 70 (PDF p. 12, page image): the size Ramsey problem on paths and cycles, which "has recently been settled by J. Beck": expected r̂(P_n,P_n)/n → ∞ but r̂(C_n,C_n)/n² → 0; Beck proved r̂(P_n,P_n) < C_1 n and r̂(C_n,C_n) < C_2 n, then unpublished (Problem 720).
• Section III.6, p. 72: Sós and Erdős observed that at most n triples of an n-set have no two meeting in exactly one point, with equality if and only if n ≡ 0 (mod 4), and conjectured that for k-subsets and n > n_0(k) the maximum is binom(n-2,k-2); proved for k = 4 by Katona and in general by Frankl (Problem 702).
• Last minute additions, p. 78 (PDF p. 20, page image): is there f with f(x)/x → ∞ such that r̂(G(n;e)) > e f(e/n) whenever e/n is large (Problem 911); the Burr-Erdős conjecture (1) r̂(G(n)) < f(c)n for graphs of bounded edge density (printed with the hat of the size Ramsey number, a misprint the next sentence corrects) and its size-Ramsey form (2) r̂(G(n)) < f(c)n.

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