Skip to main content

Upper bounds for the necklace folding problems

Authors Endre Csóka, Zoltán L.Blázsik , Zoltán Király, Dániel Lenger
Publication date 2022-06-16

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,
Pages 123-143,
ISSN 0095-8956


Separated matching
Crossing-free matching

Endre Csóka (Alfréd Rényi Institute, Budapest, Hungary)
Zoltán L.Blázsik (Alfréd Rényi Institute, Budapest, Hungary & ELKH–ELTE Geometric and Algebraic Combinatorics Research Group, Budapest, Hungary)
Zoltán Király (Department of Computer Science, ELTE Eötvös Loránd University, Budapest, Hungary)
Dániel Lenger (Department of Computer Science, ELTE Eötvös Loránd University, Budapest, Hungary)