Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cycles in a number-theoretic graph

  1. May 9, 2009 #1
    Consider the following graph:

    1.) There are n vertices labeled 1...n.
    2.) There exists an edge between vertices u and v iff label(u) | label(v) (the label of u divides the label of v).

    How many unique simple cycles does such a graph with n vertices contain?

    The exact function in terms of n may be too hard to get (lol), but growth orders are also acceptable, with appropriate proof.
    The graphs are non-directed graphs... no double-edges are allowed, but self loops are present.
    Cycles may be counted one way or both ways (that is, if 1-2-4-1 is counted as a cycle, then 1-4-2-1 may or may not be counted, as long as you make your counting method explicit).
    Last edited: May 9, 2009
  2. jcsd
  3. Jun 18, 2009 #2
    I couldn't get a general case, but a brute force method revealed for n=1 to n=24:

    1: 0
    2: 0
    3: 0
    4: 1
    5: 1
    6: 6
    7: 6
    8: 18
    9: 25
    10: 42
    11: 42
    12: 241
    13: 241
    14: 324
    15: 667
    16: 1602
    17: 1602
    18: 5511
    19: 5511
    20: 21596
    21: 32549
    22: 35434
    23: 35434
    24: 237727

    So, it would seem that the increase from n to n+1 is dependent on the number of factors of n+1, since something like 21 (factors 1, 3, 7) is a smaller percentage increase than 20 (factors 1, 2, 4, 5, 10). And obviously when n+1 is prime, no additional loops are added.

    However, because primes necessarily don't add loops, doesn't that mean that you can't have a mathematical formula for the value at n vertices, since primes aren't mapped to any known function? I guess I'm not sure how you'd go about figuring out a growth order in that case, since it's a little erratic. Anyway, I'm interested to hear your solution (assuming you've got one?)

    So, let's say L(x) is the number of loops, and F(x) is the number of factors of x. It looks like L(x)/L(x-1) <= F(x), except for a few early numbers (6 and 12).

    Last edited: Jun 19, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook