8
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ My guess is that the best one can do is by scaling the optimal situation for the divisibility graph on all the positive integers. On $1,\dotsc,14$, the graph is planar, but including $15$ we get a subgraph which is a subdivision of $K_{3,3}$, so it's not planar by Kuratowski's Theorem. Thus, an upper bound when the set starts at $2021$ instead of $1$ would be $2021 \cdot (14 + 1) - 1 = 30314$. $\endgroup$
    – Namaskaram
    Nov 6, 2021 at 19:05
  • $\begingroup$ If we can do better than this, that means that we can find a subgraph of the divisibility graph on $2021, 2022, \dotsc$ (that is not a subgraph of the full divisibility graph scaled by $2021$) that is a subdivision of $K_{3,3}$ and whose largest vertex is less than $30314$. My intuition suggests that it suffices to check that this is not possible in the case when there is no common factor of the six vertices of such a subgraph, and I'm fairly confident that in this case one can show that there is no such graph. But, there is a good deal of handwaving in all this, so… :) $\endgroup$
    – Namaskaram
    Nov 6, 2021 at 19:05
  • 1
    $\begingroup$ @Namaskaram you get a better lowest number to highest number ratio if you don't start at 1, scaling that graph gives a stronger upper bound. Clicking on the spoiler block in the answer below would have even shown you a pretty picture of such a result. $\endgroup$
    – Bass
    Nov 7, 2021 at 20:12
  • $\begingroup$ @Bass oh, this is great, I missed the spoiler in your answer. Thanks! $\endgroup$
    – Namaskaram
    Nov 7, 2021 at 20:28
  • $\begingroup$ Source: artofproblemsolving.com/community/… $\endgroup$ Nov 24, 2021 at 14:13

2 Answers 2

5
+100
$\begingroup$

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:

Image of a subgraph of the divisibility graph on the set {2021, 2022,...} that is a subdivision of the utility graph.

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.

$\endgroup$
0
4
$\begingroup$

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:

enter image description here

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:

enter image description here

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:

enter image description here

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}$.

enter image description here

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

$\endgroup$
1
  • $\begingroup$ Subdividing the graph means I think you should consider common divisor instead of pure division (the middle vertex would be the common divisor), so I think it's still easy to handle. $\endgroup$
    – justhalf
    Nov 7, 2021 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.