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.

lots of lines

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:


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

  • $\begingroup$ how does your magenta half-line begin with an arc from some $L_i$? $\endgroup$ Jul 3 '17 at 11:55
  • $\begingroup$ Sorry, meant all but one. Fixed! $\endgroup$ Jul 3 '17 at 12:00
  • $\begingroup$ 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? $\endgroup$ Jul 3 '17 at 12:03
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 3 '17 at 12:09
  • 3
    $\begingroup$ 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$. $\endgroup$ Jul 3 '17 at 12:39

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.

  • $\begingroup$ 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! $\endgroup$ Jul 4 '17 at 12:46
  • $\begingroup$ Here it is. math.stackexchange.com/questions/2344525/… $\endgroup$ Jul 17 '17 at 9:23

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.