Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  847.11048
Autor:  Erdös, Paul; Saias, Eric
Title:  Sur le graphe divisoriel. (On the divisor graph.) (In French)
Source:  Acta Arith. 73, No.2, 189-198 (1995).
Review:  Let Rf, Rg be the relations on the positive integers not exceeding x given by

aRf b <==> a|b or b|a,  aRg b <==> lcm(a,b) \leq x.

If ni Rf ni+1 for i = 1, 2,..., \ell-1, then n1, n2,..., n\ell is said to be a chain of length \ell for the relation Rf. Let f(x) denote the maximum value of \ell, and define similarly a quantity g(x) for the relation Rg. The second author [Applications des entiers à diviseurs denses (Preprint)] showed that for all x \geq 2, cx/ log x \leq f(x) \leq g(x) \leq c'x log x for certain positive constants c, c'. In this paper, the authors consider the minimum number \phi(x) of chains for the relation Rf that are required in order that every positive integer \leq x belongs to at least one such chain, and the corresponding number \gamma(x) for the relation Rg. The analogous quantity when the chains for Rf, Rg are pairwise disjoint is denoted by \phi^*(x), \gamma^*(x), respectively. It is shown that there exist positive constants c1, c2, c3 such that for all x \geq 2,

{c1 x\over log x} \leq \gamma(x) \leq \phi(x) \leq {c2 x\over log x},  c3 x \leq \gamma^*(x) \leq \phi^*(x) \leq x/2 .

Although the proofs are elementary, the establishment of the upper bound for \phi(x), particularly, is somewhat intricate.
Reviewer:  E.J.Scourfield (Egham)
Classif.:  * 11N56 Rate of growth of arithmetic functions
                   11N25 Distribution of integers with specified multiplicative constraints
                   11N37 Asymptotic results on arithmetic functions
Keywords:  divisor graph; relation in terms of least common multiple; chains for a relation; upper bound for the minimum number of chains

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

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