# A Geometric Combinatorial/Graph Theory Question

I have a combinatorics problem that seems pretty general - I'd be surprised if the answer is not known. Unfortunately, I can't seem to solve it.

The question concerns the following situation: Suppose we have a set $L$ composed of $k$ disjoint, parallel half-lines $L_i$ in $\mathbb{R}^3$ (drawn in blue below). Suppose we have another collection of $n$ pairwise-disjoint paths $P_j$ in $\mathbb{R}^3$ (drawn in the other colors with $n = 4$) so that if $P_j = \gamma_j([0, \infty))$ then $\gamma_j(0) \in L$, $\gamma_j(x)$ escapes to infinity, and $P_j \cap L_i$ is infinite for each $i, j$. Thus the $P_j$ are half-lines that bounce along the blue lines $L_i$ hitting each infinitely many times as they travel 'down' their length off to infinity.

The second image shows that in our example, by excising some initial sub-arcs of the $P_j$'s, and excising some terminal sub-arcs of the $L_i$'s, we can obtain $k$ pairwise-disjoint half-lines each of which 'begins' with an arc from some $L_i$. The question is: For a given $L_k$, is there an $n(k)$ so large that if $P_j$, $1 \leq j \leq n(k)$ are as prescribed then we may pick some $k$ of them and, using the same excision procedure, obtain $k$ pairwise-disjoint half-lines each beginning with an arc from $L$? I have been having some difficulty distilling the question into purely combinatorial terms.

This problem is coming from a problem in topology which I asked on MSE, and as exhibited there this result would be sufficient to prove a nice theorem in continuum theory:

https://math.stackexchange.com/questions/2344525/hairy-points-in-infinite-graphs-and-peano-continua

Thanks for any help! I am useless at these sorts of things.

• how does your magenta half-line begin with an arc from some $L_i$? Jul 3 '17 at 11:55
• Sorry, meant all but one. Fixed! Jul 3 '17 at 12:00
• I do not understand something. Why we can not choose any $k$ $P_j$'s for continuations of initial sub-arcs of $L_j$'s and any different $P_s$ for $(k+1)$-th path, taking its far enough terminal sub-arc? Jul 3 '17 at 12:03
• Yes, the $k+1$ was sort of redundant, was still thinking in terms of the original topology problem. As long as we can do it for $k$ of them we'll be in good shape. But it's not clear that we can definitely pick any $k$ of them and obtain the necessary arcs (that would imply what is to be show with $n(k) = k$). For example, you might try cutting one of the $L_i$'s off and weld it with $P_j$, but perhaps $P_j$ intersects all the other $L_k$'s before any other does. So there is something that needs to be shown. Jul 3 '17 at 12:09
• Is this reformulation correct? For given $k$, we want to find $n=n(k)$ with the following property. Assume that there are $n(k)$ sequences of real numbers, each of them tends to $+\infty$ and all their terms are distinct. Their terms are colored with $k$ colors, each sequence contains infinitely many terms of each color. Then we may choose numbers $x_1,\dots,x_k$ of mutually different colors (say, colors $1,\dots,k$ resp.) and from mutually different sequences $S_1,\dots,S_k$ such that for $i\ne j$, any term $y$ of color $j$, which appear after $x_i$ in the sequence $S_i$, satisfies $y>x_j$. Jul 3 '17 at 12:39

## 1 Answer

I claim that $n(k)=k$. At first, I slightly reformulate the problem.

We have a countable set $X$ of points, which is the intersection of a union of $k$ rays $r_1,\dots, r_k$, and a union of $k$ paths $p_1,\dots,p_k$. Each ray and each path is linearly ordered, and each of the sets $r_i\cap p_j\subset X$ is countable. Each (non-trivial) initial segment of a ray or a path contains only finitely many points from $X$.

We may remove an initial part from any path, and we want to reach the following property: $k$ minima $x_1,\dots,x_k$ of the $k$ sets $X\cap r_i$ all belong to different paths.

If they are not of different paths, say, green path is absent, we try to increase the number of different paths in the set $\{x_1,\dots,x_k\}$. If, say, points $x_1,x_2,x_7$ lie on a blue path, and $x_1$ appears on the blue path before $x_2$ and $x_7$, we remove the initial part of the blue path up to $x_1$ ($x_1$ is also removed). Note that the number of different colours in $\{x_1,\dots,x_k\}$ does not decrease (since $x_2$ and $x_7$ remain blue). Assume that it is not changed, that is, new $x_1$ belongs to the paths which already contains one of the points $x_2,\dots,x_k$. Proceed this way. Note that we may do only finitely many steps, because green minima on rays are "stop-points". So, after finitely many steps we increase the number of different paths in the set $\{x_1,\dots,x_k\}$, as desired.

• Thanks a ton, this works great! I will make the little adjustments for the topological case (where there might be countable/Cantor sets of intersection points between a ray and a path) and post to MSE, then link you when it's done! Jul 4 '17 at 12:46
• Here it is. math.stackexchange.com/questions/2344525/… Jul 17 '17 at 9:23