Divisibility Graph

Question

The divisibility graph of a set of integers is the graph whose vertices are the integers, two of which are joined by an edge if one divides the other.

What is the largest integer N such that the divisibility graph of the set 2021, 2022, 2023, ..., N is planar?

What will it be for the corresponding set beginning with 2022?

Answer 1

Using SageMath I found that the divisibility graph of the set $\{2021,2022,2023,\dots,N\}$ is planar for all $N$ up to and including

$15119$.

That it is not planar when 

$N=15120$

follows from the fact that now the graph includes a subdivision of $K_{3,3}$, forbidden by Kuratowski's theorem for planar graphs:

SageMath also shows that  for the set $\{2022,2023,\dots,N\}$, the value of

$15119$

remains as the most $N$ can be for the graph to be planar beginning with 2022 and beyond, maybe as far as 2047 (due to the presence of 2048 in the graph above).

The $N$th term of the sequence (likewise found with the help of SageMath) $14,23, 29,\dots,783$ gives the maximum value of $N$ such that $\{1,2,3,\dots,N\}$ is planar.

The first hundred terms of the sequence are as follows:

14, 23, 29, 39, 44, 47, 69, 79, 83, 89, 95, 95, 119, 119, 119, 143, 143, 143, 167, 167, 188, 191, 191, 191, 224, 224, 224, 224, 224, 224, 269, 269, 279, 279, 279, 279, 335, 335, 335, 335, 335, 335, 359, 359, 359, 383, 383, 383, 419, 419, 431, 431, 431, 431, 449, 449, 449, 449, 449, 449, 503, 503, 503, 503, 524, 524, 524, 524, 524, 524, 524, 524, 599, 599, 599, 623, 623, 623, 671, 671, 671, 671, 671, 671, 674, 674, 674, 674, 674, 674, 767, 767, 767, 767, 767, 767, 783, 783, 783, 783.

Answer 2

^{I managed to completely overcook my brain on this, so here's a partial answer (upper bound without proof of optimality) that may at least be helpful in explaining the basic graph and number theory bits.}

If I recall my graph theory right, a graph is planar unless it contains one of these particular subgraphs:

EDIT: big oopsie. A subdivision of either also counts. (You can split any edge by adding another vertex.) So the rest is probably just garbiage :-)

So, we are looking for two numbers: the one that creates the first K5 pattern (on the left), and the one that creates the first "utilities problem" graph on the right: all numbers that are smaller than both of those create a planar divisibility graph.

Since we are talking about actual divisibility (and not, say, sharing a factor), the K5 case is easy to solve: since the graph is fully connected, we can traverse it in order from lowest to highest, and each number must be a multiple of the previous one. Therefore the smallest solution must be 1,2,4,8 and 16, all multiplied by 2021. So the first K5 occurs at N=32336.

Which brings us to the actual point of the puzzle: what are the lowest numbers we can place on the utility graph? (If we happen to create extra edges while doing it, we don't mind.)

Let's rule out the obvious stuff first: if we put 1,2,3 on the left side, we need 6,12 and 18 on the right. Since 18 > 16, we can ignore this option as inferior to the K5 case.

So we need to put some structure into the numbers we choose. To do this, let's name the left side numbers A,B and C, and picture the sets created by their (possibly shared) prime factors:

Now, let's think about what the right side digits must look like on this diagram. An edge in the divisibility graph exists only if the number is a multiple or a divisor of the other one. In the Venn diagram above, a multiple contains all non-empty parts of a circle, and a divisor is completely contained within a circle.

So we are looking for portions of the diagram that satisfy one or the other for all the three circles.

An obvious candidate is the "everything", aka. "the union $A \cup B\cup C$", which is clearly divisible by all the factors of A, B and C. This, and multiples thereof, will surely work.

Also, the "centre bit" aka "the intersection $A \cap B \cap C$" will work, as will any subset thereof: the centre is included in each of A,B and C, so the centre will divide all of them.

These two will always work, but if we leave some areas empty, there are other options. (These are a bit too much for me right now, which is why I left this as a partial)

To show that this approach is powerful, here's a simple placement of factors that improves on the K5 solution:

Using the centre, half of the centre and a third of the centre as the right side numbers, we get 12,18 and 24 on the left, and 2,3 and 6 on the right, for a 1:12 smallest-to-largest ratio, which we can multiply by 1011 to place all the numbers in the proper range, for a new upper bound of

$\textbf{N } \mathbf{ \le 24263}$.

I'll continue when/if my brain resolidifies at some point, please feel free to use any part of this answer in your own.