Upper bounds for the necklace folding problems

Csóka, Endre and Blázsik, Zoltán and Király, Zoltán and Lenger, Dániel Antal (2022) Upper bounds for the necklace folding problems. JOURNAL OF COMBINATORIAL THEORY SERIES B, 157. pp. 123-143. ISSN 0095-8956


Download (245kB) | Preview


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 [Formula presented], 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. © 2022 Elsevier Inc.

Item Type: Article
Uncontrolled Keywords: CONSTRUCTION; COUNTEREXAMPLE; Separated matching; Crossing-free matching;
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 18 Nov 2022 12:20
Last Modified: 18 Nov 2022 12:20

Actions (login required)

Edit Item Edit Item