Endre Csóka: Upper bounds for the necklace folding problems

Abstract: 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 $\mu =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 $\mu \le 2-\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 do not necessarily have the same size. Joint work with Zoltán L. Blázsik, Zoltán Király, Dániel Lenger.