Erdos 1985 problems results combinatorial geometry

../

conjecture_p2: Erdős's two old conjectures for n points in the plane, displayed as (4) on p. 2: at least cn/(log n)^{1/2} distinct distances, and fewer than n^{1+c/log log n} unit distances, with a prize for a proof or disproof and a separate prize for the bound P_2(n) < n^{1+epsilon}.

conjecture_p4: L. Moser's question, displayed as (10) on p. 4, for the limit as R grows of the largest measure, divided by R^2, of a set without two points at distance one inside a circle of radius R, and Erdős's remark that the limit is very likely less than 1/4.

theorem_p2_line_counts: Erdős's report, in answer to Grünbaum's question on the possible numbers of lines determined by n points in the plane, that every value m > cn^{3/2} occurs except n choose 2 minus 1 and n choose 2 minus 3; the survey states it without proof.

theorem_p2_ulam_metric: Erdős's statement, made without proof in answer to a question of Ulam, that when the distance of two plane points is the sum of the absolute differences of their coordinates, the largest number of unit-distance pairs among n points is (n^2+n)/4 for n > 4 with n divisible by 4.

---

P. Erdős: Problems and results in combinatorial geometry, Discrete geometry and convexity (New York, 1982), Annals of New York Acad. Sci., 440 , pp. 1--11, New York Acad. Sci., New York, 1985 MR 87g:52001; Zentralblatt 568.51011. No notice is printed (pp. 1-2 and 10-11 read); the Crossref record for the paper's DOI 10.1111/j.1749-6632.1985.tb14533.x (read 2026-10-07) names Wiley as publisher and lists only Wiley's terms and conditions (onlinelibrary.wiley.com/termsAndConditions#vor) as its license entry, and the publisher's article page could not be read on 2026-10-07; as a Wiley journal edition, every other right is reserved.

This is a survey of open problems, in memory of Hugo Hadwiger, rather than a paper with new proofs; the results Erdős reports as his own are stated without proof. Section I (pp. 1-2) sets up P_k(n), the maximum number of unit distances among n points in k-dimensional Euclidean space, and f_k(n), the minimum number of distinct distances, and records the bounds P_2(n) = o(n^{3/2}) (Szemerédi) and f_2(n) > cn^{2/3} (L. Moser), improved to P_2(n) < n^{3/2-c} for some c > 0 (J. Beck and J. Spencer) and f_2(n) > cn^{5/7} (Fan Chung). Erdős then states, as display (4), the old conjectures he still believes, f_2(n) > cn/(log n)^{1/2} and P_2(n) < n^{1+c/log log n}, offers a prize for a proof or disproof and one for P_2(n) < n^{1+epsilon}, and remarks that P_k(n) for k >= 4 is much easier to handle than for k = 2. Section I closes with a question of Ulam on modified metrics, for which Erdős states that he proved P_2(n) = (n^2+n)/4 when n > 4 and n = 0 mod 4 under the sum-of-coordinate-differences metric. Section II (pp. 2-4) discusses Sylvester-Gallai ordinary lines and Motzkin's conjecture that for n > 13 the number of ordinary lines is at least n/2, which Erdős reports Hansen had proved in a then-unpublished proof; Grünbaum's question on the possible numbers m of lines, where Erdős reports that every m > cn^{3/2} occurs except n choose 2 minus 1 and minus 3; and conjectures on lines with many points. Section III (pp. 4-5) treats the chromatic number of the unit-distance graph and related questions, among them L. Moser's question (10) on the limit of the largest measure, divided by R^2, of a set in a circle of radius R without two points at distance one, a limit Erdős thinks very likely less than 1/4. Section IV (p. 6) treats Heilbronn's triangle problem, Section V (p. 7) Euclidean Ramsey problems, and Section VI (pp. 7-10) miscellaneous problems, among them problems on angles, unit circles, convex polygons, distances with separated values and two-distance sets.

Source: https://users.renyi.hu/~p_erdos/1985-23.pdf.

Bears on. #89: the first inequality of display (4) on p. 2, f_2(n) > cn/(log n)^{1/2}, is the affirmative answer to the problem's question; the paper records it as a conjecture (Conjecture, p. 2). #90: the second inequality of (4), P_2(n) < n^{1+c/log log n}, is the affirmative answer to the problem's question, and the paper attaches to (4) a prize offer for a proof or disproof; it records the inequality as a conjecture (Conjecture, p. 2). #232: L. Moser's question (10) on p. 4 and Erdős's remark that its limit is very likely less than 1/4; the print divides by R^2 rather than by the circle's area. Read with the area, the remark bounds below 1/4 the proportion of a large circle such a set can fill, the kind of bound the problem asks about for m_1; read with R^2 as printed, it is false, as the result page shows (Conjecture, p. 4). #606: Erdős reports, without proof, that every number m > cn^{3/2} of lines occurs except n choose 2 minus 1 and minus 3, which describes the possible values above cn^{3/2} only (Theorem, pp. 2-3).

Results.

• Conjecture, p. 2, display (4): f_2(n) > cn/(log n)^{1/2} and P_2(n) < n^{1+c/log log n} for n points in the plane, with a prize offered for a proof or disproof and one for P_2(n) < n^{1+epsilon}.
• Theorem, p. 2, unnumbered: under the sum-of-coordinate-differences metric, P_2(n) = (n^2+n)/4 for n > 4 with n = 0 mod 4; stated without proof.
• Theorem, pp. 2-3, unnumbered: every number m > cn^{3/2} of lines determined by n points in the plane occurs except n choose 2 minus 1 and n choose 2 minus 3; stated without proof.
• Conjecture, p. 4: the limit in L. Moser's question (10), the largest measure divided by R^2 of a set in a circle of radius R without two points at distance one, is very likely less than 1/4.

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