论文标题
长途途径存在
Long Alternating Paths Exist
论文作者
论文摘要
让$ p $是一组$ 2N $的凸位置，这样$ n $点是彩色的，$ n $点是彩色蓝色。 $ \ ell $的$ p $上的不交流路径是$ p_1，\ dots，p_ \ ell $ of $ p $的$ p_ \ ell $ of $ p $的点，以便（i）所有点是成对的； （ii）任何两个连续的点$ p_i $，$ p_ {i+1} $具有不同的颜色； （iii）任何两个段$ p_i p_ {i+1} $和$ p_j p_ {j+1} $具有分离的相对内部，以$ i \ neq j $。 我们表明，有一个绝对常数的$ \ varepsilon> 0 $，独立于$ n $和着色，因此$ p $始终承认一条非跨长度的交替路径至少$ $（1 + \ varepsilon）n $。结果是通过稍强的陈述获得的：在至少$（1 + \ varepsilon）$ p $的$（1 + \ varepsilon）上，始终存在非交叉的双重分离匹配。这是一种适当的颜色匹配，其段是成对的脱节，并通过公共线相交。对于这两个版本，这都是通过$ n $的添加术语线性的$ n $易于获得的$ n $的下限的第一个改进。最著名的上限是渐近的$ 4N/3+O（n）$。
Let $P$ be a set of $2n$ points in convex position, such that $n$ points are colored red and $n$ points are colored blue. A non-crossing alternating path on $P$ of length $\ell$ is a sequence $p_1, \dots, p_\ell$ of $\ell$ points from $P$ so that (i) all points are pairwise distinct; (ii) any two consecutive points $p_i$, $p_{i+1}$ have different colors; and (iii) any two segments $p_i p_{i+1}$ and $p_j p_{j+1}$ have disjoint relative interiors, for $i \neq j$. We show that there is an absolute constant $\varepsilon > 0$, independent of $n$ and of the coloring, such that $P$ always admits a non-crossing alternating path of length at least $(1 + \varepsilon)n$. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least $(1 + \varepsilon)n$ points of $P$. This is a properly colored matching whose segments are pairwise disjoint and intersected by common line. For both versions, this is the first improvement of the easily obtained lower bound of $n$ by an additive term linear in $n$. The best known published upper bounds are asymptotically of order $4n/3+o(n)$.
