Monotone paths in line arrangements (Q1869746)

The \(k\)-level of a line arrangement is an x-monotone path on the lines of the arrangement which turns in every intersection, and there are exactly \(k\) lines which pass below each point of this path. Its length is the number of turns plus one. The \(k\)-level problem for arrangements asks for the length of the longest x-monotone path in an arrangement with \(n\) lines (the best known upper bound is \(O(nk^{\frac{1}{3}})\) [\textit{T. K. Dey}, Discrete Comput. Geom. 19, 373--382 (1998; Zbl 0899.68107)] and the best known lower bound is \(ne^{\Omega(\sqrt{\log(k)})}\) [\textit{G. Tóth}, Discrete Comput. Geom. 26, 187--194 (2001; Zbl 0988.52028)] for \(n \leq 2k\)). In this paper, the authors consider the following generalization of this problem: Find the maximal length of an x-monotone path on an arrangement of \(n\) lines (without the condition that the path has to do a turn on each intersection). The best known result for a lower bound (\(\Omega(n^{5/3})\)) is due to \textit{J. Matoušek} [Discrete Comput. Geom. 6, 385--406 (1991; Zbl 0765.68210)]. The main result of this paper is a better lower bound: \(\Omega(n^{7/4})\). The authors achieve this result by constructing arrangements of \(n\) lines (which consists of some subsets of parallel lines) with x-monotone path of length \(\Omega(n^{7/4})\). At the end, they also improve a bit the trivial upper bound \({n \choose 2}+1\).