Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Can the lattice stick number of a knot be bounded by the stick number of the knot?

The stick number $S(K)$ of a knot $K$ is the fewest number of segments needed to realize it by a simple 3D polygon. The lattice stick number $S_L(K)$ is the fewest segments in a realization in the cubic lattice, with all segments parallel to a coordinate axis. For example, the stick number of the trefoil knot $K=3_1$ is 6, and its lattice stick number is 12 (the latter a result of Huh and Oh from 2005).

My question is whether it is possible to bound $S_L(K)$ by $m S(K)$, where $m$ is some multiplier factor. Ideally $m$ would be a constant, but perhaps it is more realistic to expect it to depend on the complexity of the knot (e.g., on its crossing number $cr(K)$). What I have in mind is replacing each stick in a stick realization by a bounded lattice path.

Addendum. Tracy Hall's clever example below indicates that it is unlikely that $m$ could be a constant.

share|improve this question
1  
Clarification: for lattice stick number, can a "segment" by arbitrarily long, or are you counting the total number of unit segment lengths? (Both questions look equally interesting a priori.) –  Cap Khoury Jun 15 '10 at 12:50
    
@Cap Khoury: The former. In general, the length of the sticks is not part of the definition of $S_L(K)$. One stick can consist of several collinear unit-length segments. –  Joseph O'Rourke Jun 15 '10 at 12:57
add comment

2 Answers

up vote 7 down vote accepted

I wouldn't be surprised by something like a quadratic bound, or possibly something reasonable in terms of another complexity measure for the knot, but I see no hope for making $m$ constant. Consider the following construction: given $m$, choose some large number like $N=(10m)^6$ of points uniformly at random in the unit sphere, and connect them sequentially in a cycle with straight line segments to define a knot $K$. By construction $K$ has stick number no more than $N$, but each stick has a long narrow tunnel that it must traverse in a very precise direction, which is difficult to do with only $m$ lattice sticks. Of course any one tunnel can be made shorter and wider with an affine transformation (or any small collection of tunnels, with a piecewise affine transformation) but I am convinced (without attempting a rigorous proof) that with probability approaching $1$ a knot so constructed has a lattice stick number much higher than $mS_L(K)$.

share|improve this answer
    
This is a convincing example, Tracy! Thanks! –  Joseph O'Rourke Aug 4 '10 at 13:12
add comment

The lattice stick number is obviously bounded by some function of the stick number: there are finitely many graphs with stick number at most k (because there are finitely many line segment arrangements in the plane and choices of over-under relationships on each crossing) so the lattice stick number of stick-number-k graphs is just the max of the lattice stick number of this finite set of graphs. This argument doesn't give an explicit or good bound on the number, though.

share|improve this answer
    
Thanks, David, for that clear argument! –  Joseph O'Rourke Aug 5 '10 at 16:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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