Erdos 1981 applications graph theory combinatorial methods number

../

convex_subsets_p140: Erdős's bounds n^(c_1 log n) < min C(x_1,...,x_n) < n^((1+o(1)) log n/log 2) for the least number of convex subsets of n plane points with no three on a line, proved in the paper from the Erdős–Szekeres bounds, with his expectation that log min C is asymptotic to c log^2 n.

divisor_matchings_p147: Erdős's report of his work with Pomerance on placing distinct multiples a_t of t = 1,...,n in short intervals, with the bounds on f(n), the bound F(n) < n^(3/2+ε), the open question F*(n) = O(n) for p ≤ n, the Erdős–Selfridge intervals containing only 2k multiples of k^2 primes, and Newman's coprime mapping question, proved in general by Pomerance and Selfridge as added in proof.

empty_convex_polygons_p138: Erdős's 1977 question on the least n forcing an empty convex k-gon among n plane points with no three on a line, with his report that n_4 = 5, that Ehrenfeucht proved n_5 exists, that Harborth and Morris found n_5 = 10, and that the existence of n_6 was unknown.

erdos_szekeres_bounds_p138: Erdős's restatement of the Erdős–Szekeres bounds on the least f(k) such that f(k) plane points with no three on a line contain a convex k-gon, printed as display (1) with an upper bound one below the 1935 value, with Szekeres's conjecture f(k) = 2^(k-2)+1 and the Makai–Turán value f(5) = 9.

erdos_turan_p144: The Erdős–Turán conjecture that an additive basis of order two has unbounded representation function, with Erdős's prize offer, and the multiplicative analogue he proved, given in the paper by the Ramsey-theoretic proof of Nešetřil and Rödl in a stronger form for squarefree integers with exactly m prime factors from a given sequence of primes.

large_angle_polygons_p139: Erdős's Ramsey-theoretic proof that f_ε(k) ≤ r_3(t_ε, r_4(5,k)) points with no three on a line contain a convex k-gon all but two of whose angles exceed π − ε, with his report of the Erdős–Szekeres theorem that 2^n plane points determine an angle greater than π(1 − 1/n) and of Szekeres's matching construction.

monochromatic_sums_products_p146: Erdős's questions whether a two-class split of the integers always has an infinite sequence, or for each n a finite sequence of length n, all of whose subset sums and subset products lie in one class, with his report that Hindman proved the Graham–Rothschild sums conjecture, disproved the infinite question (4), and that (5) remained open for n ≥ 3.

sums_products_p146: Erdős's conjecture that n integers give at least n^(2-ε) distinct numbers a_i + a_j and a_i a_j, the Erdős–Szemerédi bounds n^(1+c) < f(n) < n^2 exp(-c log n/log log n), and the k-fold and subset versions with the bound (2) on F(n).

unit_circles_p143: Erdős's bounds 3n/2 < h(n) ≤ n(n-1) for the largest number of distinct unit circles through at least three of n plane points, his conjecture (7) that h(n)/n^2 tends to 0 and h(n)/n to infinity, and the lattice-point question (8) that he and Harborth could not settle.

unit_distance_chromatic_p141: Erdős's report of the bounds 4 ≤ α_2 ≤ 7, α_k < 3^k (Larman and Rogers) and α_k > k^c for k > k_0(c) (Frankl) on the chromatic number of k-dimensional space, his conjecture that α_k > (1+ε)^k, proved by Frankl as added in proof, and his conjecture (6) on families avoiding one intersection size.

unit_distance_graphs_p142: Erdős's report that Wormald found a plane set whose unit distance graph has girth 5 and chromatic number 4, refuting his conjecture that excluding unit equilateral triangles forces chromatic number below 4, his weaker conjecture that large girth forces it, and his question whether the chromatic number α_2(r) for r allowed distances can grow exponentially in r.

unit_distances_p143: Erdős's conjecture, with a prize offer, that n plane points determine fewer than n^(1+ε) unit distances, with the known bounds f_2(n) = o(n^(3/2)) and f_2(n) > n^(1+c/log log n) and his remark that the lower bound is probably close to the truth.

---

P. Erdős: Some applications of graph theory and combinatorial methods to number theory and geometry, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), Colloq. Math. Soc. János Bolyai, 25, pp. 137--148, North-Holland, Amsterdam-New York, 1981 MR 83g:05001; Zentralblatt 472.10001.

Erdős surveys recent results obtained with collaborators rather than giving a systematic account. Section 1 (pp. 138--144) is geometric. It covers empty convex k-gons (n_4 = 5, n_5 = 10 by Harborth and by Morris, and n_6 not known to exist), the Erdős-Szekeres bounds 2^{k-2}+1 <= f(k) <= binom(2k-4, k-2) as printed in (1) (the 1935 upper bound is binom(2k-4, k-2)+1, and the printed one fails at k = 3), a Ramsey-theoretic proof (2) that enough points contain a convex k-gon with all but two angles above pi - eps, and a proof of (4) that the minimum number of convex subsets of n points with no three collinear lies between n^{c_1 log n} and n^{(1+o(1))log n/log 2}. It then reviews the chromatic number of unit-distance graphs in k dimensions (4 <= alpha_2 <= 7, Larman-Rogers alpha_k < 3^k, Frankl alpha_k > k^c for every c once k > k_0(c), with a note added in proof that Frankl proved the exponential lower bound), Wormald's 4-chromatic unit-distance graph of girth 5, the unit-distance count f_2(n) = o(n^{3/2}) with f_2(n) > n^{1+c/log log n} and the conjecture f_2(n) < n^{1+eps}, Scott's and Burton-Purdy's results on distinct directions, and the Corrádi-Hajnal-Erdős question whether n points not all on a line determine at least n - 2 distinct angles. On pages 143-144 Erdős defines h(n) as the largest number of distinct radius-1 circles among the circles through at least three of n points, states without proof that he could only prove 3n/2 < h(n) <= n(n-1), and states the expectation (7) that h(n)/n^2 tends to 0 while h(n)/n tends to infinity, adding that he and Harborth could not prove the lattice-point statement (8) that max_r h_r(n)/n tends to infinity. Section 2 (pp. 144--148) is number-theoretic: the Erdős-Turán conjecture, a proof by Nešetřil and Rödl of its multiplicative analogue, the Erdős-Szemerédi sum-product bounds, Hindman's disproof of the infinite sums-and-products question, and the Erdős-Pomerance and Erdős-Selfridge results on placing distinct multiples in short intervals, closing with Newman's coprime mapping question, which Pomerance and Selfridge proved as added in proof.

Source: https://users.renyi.hu/~p_erdos/1981-29.pdf. No notice is printed; the hosting archive's site footer speaks for the site, not the paper (https://users.renyi.hu/~p_erdos/, prints "(C) 2005-2007 All rights reserved. All material on this site is for scientifics purposes only."); the colloquium volume has no publisher page or DOI for this edition, so none was consulted, and no Crossref license is recorded; the term is unstated.

Bears on. #104: the site's statement, that the number of distinct unit circles through at least three of n points is o(n^2), is the first half of conjecture (7) (p. 144), and the paper states the bound 3n/2 < h(n) <= n(n-1) without proof (p. 143) (unit_circles_p143). #107: the site's statement is Szekeres's conjecture f(k) = 2^{k-2}+1 as the paper states it (p. 138), with the lower half reported proved in (1) and Makai and Turán's f(5) = 9 (erdos_szekeres_bounds_p138). #216: the paper's n_k is the site's g(k) for points with no three on a line; the paper reports g(4) = 5 and g(5) = 10 and asks whether g(6) exists (p. 138) (empty_convex_polygons_p138). #504: the reported Erdős-Szekeres theorem on angles of 2^n points and Szekeres's construction (p. 139) give the site's alpha at 2^n points, a consequence drawn on the result page, not in the paper (large_angle_polygons_p139). #838: the site's f(n) is the paper's min C(x_1,...,x_n); display (4) (p. 140) bounds it, and the site's limit question is Erdős's expectation log min C ~ c log^2 n (convex_subsets_p140). #508 and #704: the paper reports 4 <= alpha_2 <= 7, the Larman-Rogers and Frankl bounds on alpha_k, and Frankl's exponential lower bound (added in proof), and calls the limit of alpha_k^{1/k} of interest (pp. 141-142) (unit_distance_chromatic_p141). #705 and #706: Erdős's girth conjecture is the site's #705 question, and Wormald's girth-5 example (as reported) shows that k = 5 does not suffice; his question on the growth of alpha_2(r) is the site's #706 question (p. 142) (unit_distance_graphs_p142). #90: the site asks whether the reported lower bound f_2(n) > n^{1+c/log log n} gives the true order, which Erdős calls probably close to the truth; his conjecture f_2(n) < n^{1+eps} is weaker (p. 143) (unit_distances_p143). #28: the site's statement is the Erdős-Turán conjecture as the paper states it (p. 144) (erdos_turan_p144). #52: the conjecture f(n) > n^{2-eps} for the number of distinct a_i + a_j and a_i a_j is the site's statement, with the Erdős-Szemerédi bounds (1) (p. 146) (sums_products_p146). #172: question (5) (pp. 146-147) is the two-colour case of the site's question, reported open for n >= 3; the infinite question (4) is reported disproved by Hindman (monochromatic_sums_products_p146). #710, #711, #860 and #650: the paper's f(n) (interval (n, n f(n)) in place of the site's (n, n+f(n))), F(n) < n^{3/2+eps}, the open F*(n) = O(n) (with p read as prime; the paper does not say), and the Erdős-Selfridge intervals, which give the site's f(k^2) <= 2k for #650 (pp. 147-148) (divisor_matchings_p147).

Results to transcribe.

• empty_convex_polygons_p138 (result page, p. 138): For n_k the least n such that every n planar points with no three collinear contain k forming a convex k-gon with no point inside, n_4 = 5 and n_5 = 10 (Harborth, Morris independently); whether n_6 exists was unknown.
• erdos_szekeres_bounds_p138 (result page, p. 138): Szekeres's conjecture f(k) = 2^{k-2}+1 and display (1), 2^{k-2}+1 <= f(k) <= binom(2k-4, k-2) as printed; Makai and Turán's f(5) = 9.
• large_angle_polygons_p139 (result page, pp. 138-140): Display (2), f_eps(k) <= r_3(t_eps, r_4(5,k)), proved by Ramsey's theorem, and the reported angle theorems for 2^n points with display (3).
• convex_subsets_p140 (result page, p. 140): For n points with no three collinear, n^{c_1 log n} < min C(x_1,...,x_n) < n^{(1+o(1))log n/log 2}, where C counts convex subsets, proved; probably log min C ~ c log^2 n.
• unit_distance_chromatic_p141 (result page, pp. 141-142): For the unit-distance graph of k-space, 4 <= alpha_2 <= 7, alpha_k < 3^k (Larman-Rogers) and alpha_k > k^c for every c once k > k_0(c) (Frankl); added in proof, Frankl proved alpha_k > (1+eps)^k; conjecture (6) on f(n,j).
• unit_distance_graphs_p142 (result page, p. 142): Wormald's set with unit-distance graph of girth 5 and chromatic number 4, Erdős's girth conjecture, and the growth of alpha_2(r).
• unit_distances_p143 (result page, p. 143): The maximum number of unit distances among n plane points satisfies f_2(n) = o(n^{3/2}) and f_2(n) > n^{1+c/log log n}; a prize offered for a proof or disproof of f_2(n) < n^{1+eps}.
• unit_circles_p143 (result page, pp. 143-144): For h(n) the largest number of distinct unit circles passing through at least three of n plane points, 3n/2 < h(n) <= n(n-1), stated without proof; Erdős expects h(n)/n^2 -> 0 and h(n)/n -> infinity, and asks whether the lattice-point statement (8), lim max_r h_r(n)/n = infinity, holds, where h_r(n) counts the distinct circles of radius r through at least three points of the grid 0 <= x, y < n^{1/2}; (8) would imply h(n)/n -> infinity, but he and Harborth could not prove it.
• erdos_turan_p144 (result page, pp. 144-145): If f(n) counts representations n = a_i + a_j of an infinite sequence and f(n)

  0 for all n > n_0, then limsup f(n) = infinity, with a prize offered; the multiplicative analogue, proved in a stronger form by Nešetřil and Rödl's argument.

• sums_products_p146 (result page, p. 146): The Erdős-Szemerédi bounds n^{1+c} < f(n) < n^2 exp(-c log n/log log n) for the number of distinct a_i + a_j and a_i a_j, and the bound (2) on F(n).
• monochromatic_sums_products_p146 (result page, pp. 146-147): Questions (4) and (5) on monochromatic sums and products in a two-class split of the integers; Hindman disproved (4), and (5) was open for n >= 3.
• divisor_matchings_p147 (result page, pp. 147-148): The Erdős-Pomerance bounds on f(n), F(n) < n^{3/2+eps}, the question F*(n) = O(n), the Erdős-Selfridge intervals, and Newman's question.

Read status: claims checked for the statements on the result pages above, read clause by clause on the printed pages; the proofs of (2), (4) and the multiplicative Erdős-Turán analogue were read as printed.

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