## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  208.05601
Autor:  Erdös, Paul
Title:  On some applications of graph theory to number-theoretic problems (In English)
Source:  Publ. Ramanujan Inst. 1 (1968/69), 131-136 (1969).
Review:  The author proves that, if a1 < ... < ak \leq n is a sequence of integers such that the products aiaj are all distinct, then

|max k-\pi(n)| < c{n3/4 \over (log n)3/2}

where C is an absolute constant. A similar result had previously been obtained by the author with the condition ai \nmid ajak. The proof, in typical Erdös style, is based on a combinatorial lemma couched in graph theoretic language. This lemma gives an upper bound in terms of t, and t2 for the number of edges in a graph G containing no circuit of four edges and with t vertices, x1, ... ,xt, each edge being incident to one of the vertices xi, 1 \leq i < t2 < t1.
Reviewer:  I.Anderson
Classif.:  * 11B83 Special sequences of integers and polynomials
11B75 Combinatorial number theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag