11
$\begingroup$

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

For all N, is it true that integers less than or equal to N whose proper divisors have divisibility graph which is planar are more numerous than those that don't?

Using SAGE, Freddy Barrera determined those not greater than 1000 which are not planar:

32, 36, 48, 60, 64, 72, 80, 84, 90, 96, 100, 108, 112, 120, 126, 128, 132, 140, 144, 150, 156, 160, 162, 168, 176, 180, 192, 196, 198, 200, 204, 208, 210, 216, 220, 224, 225, 228, 234, 240, 243, 252, 256, 260, 264, 270, 272, 276, 280, 288, 294, 300, 304, 306, 308, 312, 315, 320, 324, 330, 336, 340, 342, 348, 350, 352, 360, 364, 368, 372, 378, 380, 384, 390, 392, 396, 400, 405, 408, 414, 416, 420, 432, 440, 441, 444, 448, 450, 456, 460, 462, 464, 468, 476, 480, 484, 486, 490, 492, 495, 496, 500, 504, 510, 512, 516, 520, 522, 525, 528, 532, 540, 544, 546, 550, 552, 558, 560, 564, 567, 570, 572, 576, 580, 585, 588, 592, 594, 600, 608, 612, 616, 620, 624, 630, 636, 640, 644, 648, 650, 656, 660, 666, 672, 675, 676, 680, 684, 688, 690, 693, 696, 700, 702, 704, 708, 714, 720, 726, 728, 729, 732, 735, 736, 738, 740, 744, 748, 750, 752, 756, 760, 765, 768, 770, 774, 780, 784, 792, 798, 800, 804, 810, 812, 816, 819, 820, 825, 828, 832, 836, 840, 846, 848, 850, 852, 855, 858, 860, 864, 868, 870, 876, 880, 882, 884, 888, 891, 896, 900, 910, 912, 918, 920, 924, 928, 930, 936, 940, 944, 945, 948, 950, 952, 954, 960, 966, 968, 972, 975, 976, 980, 984, 988, 990, 992, 996, 1000

https://puzzling.stackexchange.com/questions/112686/the-divisibility-graph-again/112731#112731

Improve this question
$\endgroup$

1 Answer 1

Reset to default
27
$\begingroup$

No, because almost all numbers have at least $4$ distinct prime factors, making the divisibility graph contain a hypercube and thus be nonplanar.

Improve this answer
$\endgroup$
5
  • 10
    $\begingroup$ With five not necessarily distinct prime divisors it contains $K_5$ $\endgroup$
    – Fedor Petrov
    Commented Nov 21, 2021 at 18:58
  • 3
    $\begingroup$ Indeed, by cataloguing these small divisor graphs and observing when they contain a $K_5$ or a $K_{3,3}$, one can produce an asymptotic formula for the number of positive integers up to $x$ with planar divisibility graphs—it would have order of magnitude $x(\log\log x)^k/\log x$ for some small $k\le3$. $\endgroup$
    – Greg Martin
    Commented Nov 22, 2021 at 16:33
  • 2
    $\begingroup$ @GregMartin I think it's a positive proportion of numbers with at most 3 prime factors, thus a constant times $x (\log \log x)^2/ \log x$. $\endgroup$
    – Will Sawin
    Commented Nov 22, 2021 at 17:00
  • $\begingroup$ @GregMartin Freddy Barrera, using SAGE, has established that precisely half of all numbers up to 26,855,026 have proper divisors whose divisibility graph is planar and half which are not. $\endgroup$
    – Bernardo Recamán Santos
    Commented Nov 22, 2021 at 23:45
  • $\begingroup$ @WillSawin The above is true again for 26,855,312, and after that for a few more numbers. However, the first instance when non-planar graphs exceed planar graphs is at 26,855,313. $\endgroup$
    – Bernardo Recamán Santos
    Commented Nov 22, 2021 at 23:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .