# Alternative parallel paths

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.)

• 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. – Stefan Kohl Apr 29 '16 at 21:53
• Explaining the example figure---the significance of the colors---would be a start toward responding to Stefan. – Joseph O'Rourke Apr 30 '16 at 0:56
• 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? – Ilya Bogdanov May 4 '16 at 12:46
• @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. – Tobias Schlemmer Jul 21 '18 at 13:07
• 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). – Tobias Schlemmer Jul 21 '18 at 13:30

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".
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.