##
**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 a_{1} < ... < a_{k} \leq n is a sequence of integers such that the products a_{i}a_{j} are all distinct, then |**max** k-\pi(n)| < c{n^{3/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 a_{i} \nmid a_{j}a_{k}. 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 t_{2} for the number of edges in a graph G containing no circuit of four edges and with t vertices, x_{1}, ... ,x_{t}, each edge being incident to one of the vertices x_{i}, 1 \leq i < t_{2} < t_{1}.

**Reviewer: ** I.Anderson

**Classif.: ** * 11B83 Special sequences of integers and polynomials

11B75 Combinatorial number theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag