论文标题
项链折叠问题的上限
Upper bounds for the necklace folding problems
论文作者
论文摘要
项链可以被视为$ n $红色和$ n $蓝色珠子的循环清单，目标是将其折叠成两种，并找到一对大型颜色的珠子的大型搭配。我们给出了关于项链折叠问题的猜想的反例，也称为分离的匹配问题。猜想（由三组作者独立给出）指出，$μ= \ frac {2} {3} $，其中$μ$是“覆盖”珠子与珠子总数的比例。 我们通过提供建筑物来反驳这种猜想，该建筑证明了$μ\ le 2 \ nolinebreak -\ nolinebreak \ sqrt 2 <0.5858 $。我们的构造也适用于同质模型：当我们匹配相同颜色的珠子时。此外，我们还考虑了两个颜色类不一定具有相同大小的问题。
A necklace can be considered as a cyclic list of $n$ red and $n$ blue beads in an arbitrary order, and the goal is to fold it into two and find a large cross-free matching of pairs of beads of different colors. We give a counterexample for a conjecture about the necklace folding problem, also known as the separated matching problem. The conjecture (given independently by three sets of authors) states that $μ=\frac{2}{3}$, where $μ$ is the ratio of the `covered' beads to the total number of beads. We refute this conjecture by giving a construction which proves that $μ\le 2 \nolinebreak - \nolinebreak \sqrt 2 < 0.5858$. Our construction also applies to the homogeneous model: when we are matching beads of the same color. Moreover, we also consider the problem where the two color classes not necessarily have the same size.
