<p>The number of graphs on <span class="math-container">$n$</span> vertices is
<span class="math-container">$$2^{\frac{n(n-1)}{2}}.$$</span></p>
<p>The number of embeddings of a degree 4 planar graph with <span class="math-container">$n$</span> vertices is at most <span class="math-container">$6^n$</span>. (If you know the clockwise order of the neighbors of each vertex, this determines the embedding.) So there are at most<br />
<span class="math-container">$$2^{\frac{n(n-1)}{2}} 6^n $$</span> different embeddings of degree 4 planar graphs with <span class="math-container">$n$</span> vertices.</p>
<p>Suppose you have a diagram of a knot with n crossings. This gives an embedding of a degree 4 planar graph with <span class="math-container">$n$</span> vertices. And at each crossing, you have a choice of putting the first strand over or under the second. Thus, there are at most
<span class="math-container">$$
2^n 2^{\frac{n(n-1)}{2}} 6^n
$$</span>
different knot diagrams with at most <span class="math-container">$n$</span> crossings.</p>
<p>This is an immense overestimate.</p>

CC BY-SA 4.0
2023-06-07T14:51:15.800Z
2023-06-07T14:56:18.963Z
2023-06-07T14:56:18.963Z
Peter Shor 
<p>One result in knot theory is that <a href="https://arxiv.org/abs/1908.04073" rel="nofollow noreferrer">link crossing number is NP-hard</a>. Another result is that <a href="https://arxiv.org/abs/1508.06720" rel="nofollow noreferrer">the equivalence problem for knots and links is elementary recursive</a>. So, given that the equivalence problem is elementary recursive, wouldn't the crossing number be elementary recursive? Say that I have a knot with 42 crossings and I want to find out its minimal crossing number. Once I have all other knots up to and including 42 crossings then I can solve that problem with an upper bound elementary recursive by checking for equivalence with all other knots. But generating all other knots up to and including 42 crossings must not be worse than elementary recursive for it to work. Is it? I read about recent tabulations and could not find the upper bounds. I assume that if it is super-exponential then it is a bottleneck to generate the objects, but if we know that it is at least as efficient as equivalence then it could be claimed that knot crossing number problem has upper bound elementary recursive, and maybe link crossing number too.</p>
<p>I hypothesize that the answer is no: the number of objects for every crossing number grows too fast, but I'm still trying to figure it out and will try and learn more about it.</p>

<computational-geometry><topology>
Is minimum knot crossing number elementary recursive?
Niklas Rosencrantz
# Is minimum knot crossing number elementary recursive?

(Asked by: username_0 on 2023-05-28)

One result in knot theory is that [link crossing number is NP-hard](https://arxiv.org/abs/1908.04073). Another result is that [the equivalence problem for knots and links is elementary recursive](https://arxiv.org/abs/1508.06720). So, given that the equivalence problem is elementary recursive, wouldn't the crossing number be elementary recursive? Say that I have a knot with 42 crossings and I want to find out its minimal crossing number. Once I have all other knots up to and including 42 crossings then I can solve that problem with an upper bound elementary recursive by checking for equivalence with all other knots. But generating all other knots up to and including 42 crossings must not be worse than elementary recursive for it to work. Is it? I read about recent tabulations and could not find the upper bounds. I assume that if it is super-exponential then it is a bottleneck to generate the objects, but if we know that it is at least as efficient as equivalence then it could be claimed that knot crossing number problem has upper bound elementary recursive, and maybe link crossing number too.

I hypothesize that the answer is no: the number of objects for every crossing number grows too fast, but I'm still trying to figure it out and will try and learn more about it.

**Tags:** computational-geometry, topology

---

## 1 answers

### Answer by username_1 on 2023-06-07. Score: 5 | Accepted answer

The number of graphs on $n$ vertices is
$$2^{\frac{n(n-1)}{2}}.$$

The number of embeddings of a degree 4 planar graph with $n$ vertices is at most $6^n$. (If you know the clockwise order of the neighbors of each vertex, this determines the embedding.) So there are at most  
$$2^{\frac{n(n-1)}{2}} 6^n $$ different embeddings of degree 4 planar graphs with $n$ vertices.

Suppose you have a diagram of a knot with n crossings. This gives an embedding of a degree 4 planar graph with $n$ vertices. And at each crossing, you have a choice of putting the first strand over or under the second. Thus, there are at most
$$
2^n 2^{\frac{n(n-1)}{2}} 6^n
$$
different knot diagrams with at most $n$ crossings.

This is an immense overestimate.


---

