A necklace can be considered as a cyclic list of n red and n blue beads in an arbitrary order. In the necklace folding problem the goal is to find a large crossing-free matching of pairs of beads of different colors in such a way that there exists a “folding” of the necklace, that is a partition into two contiguous arcs, which splits the beads of any matching edge into different arcs.
We give counterexamples for some conjectures about the necklace folding problem, also known as the separated matching problem. The main conjecture (given independently by three sets of authors) states that μ = 2 3 , where μ is the ratio of the maximum number of matched beads to the total number of beads.
We refute this conjecture by giving a construction which proves that μ ≤ 2 − √2 < 0.5858 0.66. Our construction also applies to the homogeneous model when we match beads of the same color. Moreover, we also consider the problem where the two color classes do not necessarily have the same size
Endre Csóka, Zoltán L. Blázsik, Zoltán Király, Dániel Lenger,
Upper bounds for the necklace folding problems,
Journal of Combinatorial Theory, Series B,
Volume 157,
2022,
Pages 123-143,
ISSN 0095-8956
DOI: https://doi.org/10.1016/j.jctb.2022.05.012
Keywords:
Separated matching
Crossing-free matching
Counterexample
Construction