There are $n$ non-intersecting strings (with ends $x_1,\dots, x_n$ and $y_1,\dots, y_n$). An additional string intersects the first $n$ strings somehow. All the intersections are simple (vertices of degree $4$). The edges incident to an intersection points are divided into two pairs of opposite edges (two opposite edges in a pair belong to the same string).

We consider sets of $n$ paths in the graph formed by these $n+1$ strings which have three properties: 1) paths have the same ends as the original $n$ strings (i.e. each path connects $x_i$ with $y_i$ for some $i$);
2) paths have no common edges;
3) paths can have common vertices but their intersections are not transversal. Two path intersect transversly if each path contains a pair of opposite edges at the intersection point. In this sense, the intersections of the additional string with the other strings are all transversal.

The original $n$ strings satisfy these three conditions.

Is there a number $N=N(n)$ such that if the number of intersections of the additional string with the other strings is greater than $N$, we can find a set of $n$ paths that satisfies the conditions and differs from the original strings?

The example below presents a configuration where there are two different sets of paths (the original strings (left) and an alternative set of paths (right)).

Warning: the example is braid-like since all the strings are monotonic, but in general case the additional string can go up and down at its discretion.

(Example image included by J.O'Rourke.)


  • 3
    $\begingroup$ I think it would make it more likely that you get an answer if you put a little more effort into the formulation of your question. $\endgroup$
    – Stefan Kohl
    Apr 29, 2016 at 21:53
  • 2
    $\begingroup$ Explaining the example figure---the significance of the colors---would be a start toward responding to Stefan. $\endgroup$ Apr 30, 2016 at 0:56
  • $\begingroup$ It seems that some intersections on the right figure are transversal, so this figure doesn't provide an example of what you wish. Am I right? $\endgroup$ May 4, 2016 at 12:46
  • $\begingroup$ @IlyaBogdanov: It is not clear from the description. The fourth strings seems to intersect with the other strings in only 12 points. The other six are non-crossings. Ther result from the non-planarity of the graph. $\endgroup$ Jul 21, 2018 at 13:07
  • $\begingroup$ I propose to rename $n$ in $N(n)$ to something different, e.g. $m$. As this number only makes sense if $m>n$. As you have always at least $n$ paths (those corresponding to the orignal $n$ strings). $\endgroup$ Jul 21, 2018 at 13:30

1 Answer 1


the answer is yes, simply because there are at least two different paths for $n\ge 2$.
Assuming that at least two different paths exist for $n\ge 2$ one can interpret the 1st path as a $0$bit and the 2nd one as a $1$bit, which proves that we can assemble $2^m$ different paths from $m$ of those two "bits".

While that construction answers the question as it has been posed, I strongly suspect that the PO had something different in mind.

What seems more interesting is the question for the minimal height (i.e. vertical distance between $x_i$ and $y_i$) for paths that contain a given sequence of horizontal permutations of the colors of vertical segments; here the key observation seems to be that the height difference between permutations, that are adjacent in the sequence, equals the maximal "left-shift" of a color between those permutations.

  • $\begingroup$ I can not take any different paths because I want to avoid transversal intersections. I means the paths must turn at the intersection points with the other paths. $\endgroup$
    – nim
    May 1, 2016 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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