Walks in the divisor graph

Among Paul Erdős's interests, two fields stand out more often than others: number theory and graph theory. It is therefore no surprise that he eventually became interested in the divisor graph, a mathematical object that lies precisely at the crossroads of these two subjects.

To construct a divisor graph, start by fixing an integer n, called the index of the graph. The vertices of the graph are then the integers 1, 2... up to n. An edge connects two distinct integers in this graph if the larger of the two is a multiple of the smaller (or equivalently, if the smaller divides the larger). For example, in the divisor graph of index n = 6 (a drawing of which appears below), there are 6 vertices; vertex 1 is connected to all the others, vertex 2 to 1, 4 and 6, vertex 3 only to 1 and 6, and that already accounts for all the edges (the edges connecting 4 to 1, 4 to 2, 5 to 1, 6 to 1, 6 to 3 have already been drawn).

Divisor graph of index 6.

Some properties are immediately apparent: vertex 1 is connected to every other vertex; a vertex corresponding to a prime number is connected only to its multiples and to 1, hence to relatively few vertices; conversely, an integer with many divisors is connected to numerous vertices.

These observations can give some idea of the structure of the divisor graph, but that structure remains hard to grasp, and hence to analyze, once the initially chosen integer n becomes large. In the drawing above, the divisor graph of index 100 looks rather tangled, even though its "circular" layout already hints at a few intriguing patterns. For significantly larger values of n, it is wishful thinking to expect to understand the graph from one of its drawings.