There is a long path in the divisor graph. (English) Zbl 0536.05041

Pollington, Andrew D.

Ars Comb. 16-B, 303-304 (1983).

In this paper a construction is given which produces a ”long” simple path in the ”divisor” graph among natural numbers up to n. The idea is as follows: by the prime number theorem, for sufficiently large n one can get many (m) primes so that the product of any \(k+1\) of them (for appropriate k) is less than n. One can then find a long path (of length twice the binomial coefficient m choose k) among sets having no more than \(k+1\) elements in the inclusion graph on subsets of an n element set; which corresponds to a simple path as desired in the divisor graph. Suitable choices of m and k give a path whose length is \(n\quad \exp \quad((-2+\epsilon)(\log n \log \log n)^{1/2})\).

Reviewer: D.Kleitman

MSC:

05C38	Paths and cycles
05C99	Graph theory

Keywords:

maximal path length; ”divisor” graph