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