Publications of Paul Erdos

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₁ < ... < a_k \leq n is a sequence of integers such that the products a_ia_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_ja_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₂ for the number of edges in a graph G containing no circuit of four edges and with t vertices, x₁, ... ,x_t, each edge being incident to one of the vertices x_i, 1 \leq i < t₂ < t₁.
Reviewer: I.Anderson
Classif.: * 11B83 Special sequences of integers and polynomials
11B75 Combinatorial number theory

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.

Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry

Probabability Personalia About Paul Erdös Publication Year Home Page

Books	Problems	Set Theory	Combinatorics	Extremal Probl/Ramsey Th.
Graph Theory	Add.Number Theory	Mult.Number Theory	Analysis	Geometry
Probabability	Personalia	About Paul Erdös	Publication Year	Home Page