##
**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 R_{f}, R_{g} be the relations on the positive integers not exceeding x given by aR_{f} b <==> a|b or b|a, aR_{g} b <==> lcm(a,b) \leq x. If n_{i} R_{f} n_{i+1} for i = 1, 2,..., \ell-1, then n_{1}, n_{2},..., n_{\ell} is said to be a chain of length \ell for the relation R_{f}. Let f(x) denote the maximum value of \ell, and define similarly a quantity g(x) for the relation R_{g}. 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 R_{f} 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 R_{g}. The analogous quantity when the chains for R_{f}, R_{g} are pairwise disjoint is denoted by \phi^*(x), \gamma^*(x), respectively. It is shown that there exist positive constants c_{1}, c_{2}, c_{3} such that for all x \geq 2,

{c_{1} x\over log x} \leq \gamma(x) \leq \phi(x) \leq {c_{2} x\over log x}, c_{3} 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