Erdos 1969 applications graph theory number theory

../

conjecture_p81: Erdős's 1969 conjecture on 3-graphs with 3n vertices and n^3 + 1 triples, stated after Turán's hypergraph problem and his (5,3) conjecture; the printed origin of Problem 794.

equation_9: The asymptotic for the threshold size forcing an integer with p representations as a product of two terms, restated from the 1964 Israel Journal paper.

inequality_1: The two-sided bound for the largest sequence up to x in which no term divides the product of two others, with the outline of the tree argument for the upper bound.

inequality_10: A special result Erdős states without proof, bracketing u_3(n) between n log log n/log n plus two second-order terms printed with denominator (log n)^2; the printed source of Problem 796's question.

inequality_11: The two-sided bound for the least size forcing r terms with pairwise equal greatest common divisors, with the Erdős–Rado intersection conjecture that would make the lower bound sharp.

inequality_2: Erdős's 1969 request for an asymptotic constant in the second term of the no-divisor-of-a-product bound, the printed origin of Problem 793.

inequality_3: The two-sided bound for sequences up to x in which no term divides the product of r others, stated as a generalization of the method of (1).

inequality_6: The upper bound for sequences up to x all of whose subset products are distinct, quoted from the 1966 Hungarian paper.

inequality_7: Erdős's conjectured sharp form of the distinct-subset-product bound, with the primes and their squares as the extremal example.

question_p82: The paper's second-to-last question, on two sequences up to n with all cross products distinct.

---

P. Erdős: Some applications of graph theory to number theory, The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , pp. 77--82, Springer, Berlin, 1969 MR 40 #4149; Zentralblatt 187,210.

This survey collects results in which extremal graph theory bounds the size of integer sequences with multiplicative constraints. Its central examples are inequality (1), that the largest sequence up to x in which no term divides the product of two others has size between pi(x) + c_1 x^{2/3}/(log x)^2 and pi(x) + c_2 x^{2/3}/(log x)^2, its r-fold generalization (3) with exponent 2/(r+1), and inequality (4), that the largest sequence up to x with all pairwise products a_i a_j distinct has size pi(x) + Theta(x^{3/4}/(log x)^{3/2}); the proofs represent each integer as u times v and read the divisibility condition off the resulting graph, which must be a tree in the first case and contain no four-cycle in the second. Erdős also records that a sequence up to x with all subset products distinct has at most pi(x) + c_6 x^{1/2}/log x terms (6), and conjectures the sharper form (7) with the primes and their squares extremal. Further sections state, as the basic lemma, that every G_r(n; c n^{r - eps_{k,r}}) contains a complete r-partite K_r(k,...,k), cite Kővári-Sós-Turán for eps_{k,2} >= 1/k (printed eps_{k,r} >= 1/k), suggest that eps_{k,2} = 1/k is the best value, state Turán's unsolved hypergraph problem f(n,r,s) with his conjecture f(2n,3,5) = n^2(n-1) + 1, and give bounds (11) on the least number f(r,n) of integers up to n forcing r of them with equal pairwise gcds, whose lower bound would give the correct order of magnitude given the Erdős-Rado sunflower-type conjecture. The final section poses the finite questions on sequences with distinct multiplicative representations, asking whether max k = n + o(n) and whether kq < c n^2 / log n for two sequences with distinct products a_i b_j. The site cites the paper as a source of problems 490, 535, 714, 793, 794, 795, 796 and 951: for these divisibility, gcd and distinct-product bounds and questions, for Erdős's guess that the graph exponent eps_{k,2} = 1/k is best possible, and for Erdős's own 3-graph conjecture on p. 81.

The copy read for this card is the six-page file from the Rényi Institute's Erdős archive (printed pp. 77--82 are PDF pp. 1--6; its text layer garbles the displayed exponents). Read status: claims checked for displays (1), (2), (3), (6), (7), (9), (10) and (11) and for the two-sequence question on pp. 81--82, each read clause by clause on the page images on 2026-09-18; the outline of the upper bound of (1) was read; displays (4), (5), (8) and (12) were read as statements only; no proof is checked here. Display (10) prints its two second-order terms with the denominator $(\log n)^2$, as recorded on its result page. Claims checked also, for the Turán paragraph of p. 80 (PDF p. 4) and the 3-graph conjecture that opens p. 81 (PDF p. 5), "Every $G_3(3n;n^3+1)$ contains either a $G_3(4;3)$ or a $G_3(5;7)$", read clause by clause on the page images and paged at conjecture_p81; the paper gives no argument for it. Claims checked also, for the closing question of p. 82 (PDF p. 6), the real-number modification of the paper's problems, read clause by clause on the page image; no argument is given. No copyright or license line is printed on the pages (printed pp. 77--82 of Lecture Notes in Mathematics 110); the publisher's article page was not consulted, and the Crossref record for DOI 10.1007/bfb0060107 (read 2026-10-02) names only Springer's text-and-data-mining terms (http://www.springer.com/tdm) and no Creative Commons license, every other right reserved.

Source: https://users.renyi.hu/~p_erdos/1969-14.pdf.

Bears on. #793: displays (1) and (2), printed pp. 77--78 (PDF pp. 1--2), the two-sided bound and the asymptotic question. #796: equation (9) and display (10), printed p. 80 (PDF p. 4), the asymptotic of $u_p(n)$ and the second-order bounds for $u_3(n)$ as printed. #795: displays (6) and (7), printed p. 79 (PDF p. 3), the subset-product bound and the conjectured sharp form. #490: the question on printed pp. 81--82 (PDF pp. 5--6), whether distinct products $a_ib_j$ force $kq<cn^2/\log n$. #535: display (11), printed p. 81 (PDF p. 5), the bounds on $f(r,n)$ and the sunflower conjecture. #794: the conjecture on printed p. 81 (PDF p. 5), "Every $G_3(3n;n^3+1)$ contains either a $G_3(4;3)$ or a $G_3(5;7)$", the site's [Er69, p. 81] source, preceded on p. 80 by Turán's $f(2n,3,5)=n^2(n-1)+1$ and the limit $\delta_{r,s}$ (conjecture_p81). #714: the lemma paragraph on printed p. 80 (PDF p. 4), where, after Kővári, Sós and Turán's bound (printed $\varepsilon_{k,r}\ge1/k$; their theorem is the graph case), Erdős writes "In fact probably $\varepsilon_{k,2}=1/k$ is the best value for $\varepsilon_{k,2}$", with Brown's result for $k=3$ and the cases $k>3$ open: the exponent form of the problem's question; the site's key [Er69]. #425: inequality (4), printed p. 78 (PDF p. 2, page image), for sequences up to $x$ with all products $a_ia_j$ distinct, $\pi(x)+c_4x^{3/4}/(\log x)^{3/2}<\max k<\pi(x)+c_3x^{3/4}/(\log x)^{3/2}$, cited to [3] [4] and proved through graphs with no 4-cycle, the two-sided bound for the problem's $F(n)$ whose constant it asks for; the closing paragraph of p. 78, continued on p. 79 (PDF p. 3), raises the products of $r$ distinct $a$'s, "I am not able to give a very satisfactory estimation for $\max k-\Pi(x)$ if $r>2$", the problem's second question, with no bound stated. #951: the closing question on printed p. 82 (PDF p. 6, page image), "Finally many of these problems can be modified as follows: Let $a_1<\ldots<a_k$ be a sequence of real numbers. Assume that any two of the numbers $\prod a_i^{\alpha_i}$ differ by at least one. Is it true that $\max k=\Pi(n)$?" (the range $a_k\le n$ is implicit, as in the paper's preceding problems), the finite form of the problem's question that Erdős's 1980 survey recalls in a footnote; display (6) on p. 79 (PDF p. 3) is the integer subset-product bound, a different finite question kept separate on the problem page; the site's key [Er69, p. 82].

Results to transcribe.

• Conjecture, p. 81: every $G_3(3n;n^3+1)$ contains either a $G_3(4;3)$ or a $G_3(5;7)$; stated after Turán's hypergraph problem $f(n,r,s)$ and his conjecture $f(2n,3,5)=n^2(n-1)+1$ (p. 80).

• Inequality (1), p. 77: For sequences up to x in which no term divides the product of two others, pi(x) + c_1 x^{2/3}/(log x)^2 < max k < pi(x) + c_2 x^{2/3}/(log x)^2.

• Display (2), p. 78: the question whether max k = pi(x) + c x^{2/3}/(log x)^2 + o(x^{2/3}/(log x)^2) for an absolute constant c.

• Inequality (3), p. 78: If no term divides the product of r others, then pi(x) + c_1^{(r)} x^{2/(r+1)}/(log x)^2 < max k < pi(x) + c_2^{(r)} x^{2/(r+1)}/(log x)^2.

• Inequality (4), p. 78: If all pairwise products a_i a_j are distinct, then pi(x) + c_4 x^{3/4}/(log x)^{3/2} < max k < pi(x) + c_3 x^{3/4}/(log x)^{3/2}, proved via graphs with no four-cycle.

• Inequality (6), p. 79: If all subset products of the sequence are distinct then max k < pi(x) + c_6 x^{1/2}/log x; display (7) conjectures the sharper pi(x) + pi(x^{1/2}) + o(x^{1/2}/log x), with primes and their squares extremal.

• Equation (9), p. 80: u_p(n), the least k such that any k integers up to n give some m with at least p representations as a product a_i a_j, satisfies u_p(n) = (1+o(1)) n (log log n)^{r-1} / ((r-1)! log n) for 2^{r-1} < p <= 2^r.

• Inequality (10), p. 80: stated without proof, n log log n/log n + c_9 n/(log n)^2 < u_3(n) < n log log n/log n + c_10 n/(log n)^2, "It is not clear whether (10) can be sharpened."

• Inequality (11), p. 81: The least f(r,n) forcing r terms with equal pairwise greatest common divisors satisfies exp(c_r log n / log log n) < f(r,n) < n^{3/4+epsilon}; that the lower bound gives the correct order of magnitude would follow from the Erdős-Rado intersection conjecture.

• Question, pp. 81--82: for two sequences up to n with all products a_i b_j distinct, is kq < c n^2/log n?

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