×

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

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
PDFBibTeX XMLCite