https://m2.mtmt.hu/ hun 2026-04-29 11:53 JournalArticle 33056151 ADMIN_APPROVED true Alfréd Rényi Institute, Budapest, Hungary ELKH–ELTE Geometric and Algebraic Combinatorics Research Group, Budapest, Hungary Department of Computer Science, ELTE Eötvös Loránd University, Budapest, Hungary Export Date: 18 August 2022 CODEN: JCBTB Funding details: ERC-2018-SYG 810115 Funding details: Hungarian Scientific Research Fund, OTKA, FK 132524, SNN 132625 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH Funding text 1: The research was supported by Dynasnet European Research Council Synergy project (ERC-2018-SYG 810115).The research was supported by the Hungarian National Research, Development and Innovation Office, OTKA grant no. SNN 132625.This research was partially supported by the Hungarian National Research, Development and Innovation Office, OTKA grant no. FK 132524. 0 false 2026-01-02T01:35:22.351+0000 2023-02-10T15:08:39.945+0000 2022-08-18T10:21:26.049+0000 true 10015168 Szakonyi Erzsebet /api/admin/10015168 Admin true 10015168 2024-06-18T10:25:23.928+0000 2023-02-10T15:08:40.179+0000 true 10071503 Szabó Regina /api/admin/10071503 Admin true true false true 24 24 /api/publicationtype/24 PublicationType 1 true 24 JournalArticle true 10000059 Article true 24 24 /api/publicationtype/24 PublicationType 1 true 24 JournalArticle /api/subtype/10000059 Szakcikk SubType 101 true 10000059 true 1 /api/category/1 Category true 1 Csóka, Endre Upper bounds for the necklace folding problems true true /api/journal/2387 REVIEWED true false 2387 false 2387 true 0095-8956 1096-0902 Journal FOREIGN 157 123 143 123 21 2022 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. 2022 true true true false false GOLD 2026-01-02 true https://doi.org/10.1016/j.jctb.2022.05.012 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 D1 false 10010476,10055050 false false false 2022-11-16T11:47:51.241+0000 Diszkrét Matematika (RAMKI); MTA-ELTE Geometriai és algebrai kombinatorika k... (ELTE / TTK / Mat_I); Számítógéptudományi Tanszék (ELTE / TTK / Mat_I) 4 23 3 4 0 true Language 10002 /api/language/10002 Angol English true 2 true PersonAuthorship 103160254 /api/authorship/103160254 1 0.25 true false true Author 10029947 /api/author/10029947 Csóka Endre true 10029947 true Csóka Endre true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PersonAuthorship 103160255 /api/authorship/103160255 2 0.25 false false true Author 10055050 /api/author/10055050 Blázsik Zoltán true 10055050 true Blázsik Zoltán true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PersonAuthorship 103160256 /api/authorship/103160256 3 0.25 false false true Author 10010476 /api/author/10010476 Király Zoltán true 10010476 true Király Zoltán true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PersonAuthorship 103160257 /api/authorship/103160257 4 0.25 false true true Author 10076665 /api/author/10076665 Lenger Dániel Antal true true Lenger Dániel Antal true false false AuthorshipType 1 /api/authorshiptype/1 0 true 0 true false true PublicationIdentifier 21593337 /api/publicationidentifier/21593337 PlainSource 6 /api/publicationsource/6 PublicationSourceType 10001 /api/publicationsourcetype/10001 true true true DOI DOI https://doi.org/@@@ true true 6 true GOLD true IDENTICAL 10.1016/j.jctb.2022.05.012 https://doi.org/10.1016/j.jctb.2022.05.012 false true PublicationIdentifier 21593338 /api/publicationidentifier/21593338 PlainSource 1 /api/publicationsource/1 PublicationSourceType 10003 /api/publicationsourcetype/10003 false true true WoS WoS https://www.webofscience.com/wos/woscc/full-record/@@@ true true 1 true IDENTICAL 000816900100003 https://www.webofscience.com/wos/woscc/full-record/000816900100003 false true PublicationIdentifier 22115609 /api/publicationidentifier/22115609 SwordSource 36 /api/publicationsource/36 PublicationSourceType 10007 /api/publicationsourcetype/10007 true true true REAL REAL http://real.mtak.hu/@@@ true true 36 true GREEN true 153735 http://real.mtak.hu/153735 false true PublicationIdentifier 24126873 /api/publicationidentifier/24126873 SwordSource 92 /api/publicationsource/92 PublicationSourceType 10007 /api/publicationsourcetype/10007 true true true EDIT EDIT https://edit.elte.hu/xmlui/handle/10831/@@@ true true 92 true GREEN true 89915 https://edit.elte.hu/xmlui/handle/10831/89915 false true PublicationIdentifier 21593339 /api/publicationidentifier/21593339 PlainSource 3 /api/publicationsource/3 PublicationSourceType 10003 /api/publicationsourcetype/10003 false true true Scopus Scopus http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-@@@ true true 3 true 85132553440 http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85132553440 false true PublicationIdentifier 18525750 /api/publicationidentifier/18525750 PlainSource 37 /api/publicationsource/37 PublicationSourceType 10007 /api/publicationsourcetype/10007 true true true arXiv http://arxiv.org/abs/@@@ true true 37 true 2005.12603 http://arxiv.org/abs/2005.12603 false true Classification 10018 /api/classification/10018 true true Classification 10004 /api/classification/10004 true true Classification 10003 /api/classification/10003 true true Classification 10007 /api/classification/10007 true true Classification 10024 /api/classification/10024 true true Keyword 3015 /api/keyword/3015 true 3015 true Keyword 2356254 /api/keyword/2356254 true true Keyword 2662090 /api/keyword/2662090 true true Keyword 2662091 /api/keyword/2662091 true true SjrRating 11290595 /api/sjrrating/11290595 13 0.1 journal RatingType 10002 /api/ratingtype/10002 sjr true true ClassificationExternal 1703 /api/classificationexternal/1703 true 1703 true D1 DIRECT true true Reference 32963931 /api/reference/32963931 1 false true Reference 32963932 /api/reference/32963932 2 false true Reference 32963933 /api/reference/32963933 3 false true Reference 32963934 /api/reference/32963934 4 false true Reference 32963935 /api/reference/32963935 5 false true Reference 32963936 /api/reference/32963936 6 false true Reference 32963937 /api/reference/32963937 7 false true Reference 32963938 /api/reference/32963938 8 false true Reference 32963939 /api/reference/32963939 9 false true Reference 32963940 /api/reference/32963940 10 false true Reference 32963941 /api/reference/32963941 11 false true /api/publication/33056151 <div class="JournalArticle Publication long-list"> <div class="authors"> <img title="Forrásközlemény" style="float: left" src="/frontend/resources/grid/publication-core-icon.png"> <img title="Idézőközlemény" style="float: left" src="/frontend/resources/grid/publication-citation-icon.png"> <div class="autype autype0"> <span class="author-name" mtid="10029947"><a href="/gui2/?type=authors&mode=browse&sel=10029947" target="_blank">Csóka Endre ✉ (<span class="authorship-author-name">Csóka Endre</span> <span class="authorAux-mtmt"> matematika</span>) </a> </span> <span class="author-affil"><span title="Rényi Alfréd Matematikai Kutatóintézet">RAMKI</span>/Diszkrét Matematika</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10055050"><a href="/gui2/?type=authors&mode=browse&sel=10055050" target="_blank">Blázsik Zoltán ✉ (<span class="authorship-author-name">Blázsik Zoltán</span> <span class="authorAux-mtmt"> kombinatorika, gráfelmélet</span>) </a> </span> <span class="author-affil"><span title="Rényi Alfréd Matematikai Kutatóintézet">RAMKI</span>/Diszkrét Matematika; <span title="Eötvös Loránd Tudományegyetem">ELTE</span>/<span title="Természettudományi Kar">TTK</span>/<span title="Matematikai Intézet">Mat_I</span>/MTA-ELTE Geometriai és algebrai kombinatorika kutatócsoport</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10010476"><a href="/gui2/?type=authors&mode=browse&sel=10010476" target="_blank">Király Zoltán ✉ (<span class="authorship-author-name">Király Zoltán</span> <span class="authorAux-mtmt"> diszkrét matematika, kombinatorikus optimalizál...</span>) </a> </span> <span class="author-affil"><span title="Eötvös Loránd Tudományegyetem">ELTE</span>/<span title="Természettudományi Kar">TTK</span>/<span title="Matematikai Intézet">Mat_I</span>/Számítógéptudományi Tanszék</span> ;&nbsp;&nbsp;&nbsp; <span class="author-name" mtid="10076665"><a href="/gui2/?type=authors&mode=browse&sel=10076665" target="_blank">Lenger Dániel Antal ✉ (<span class="authorship-author-name">Lenger Dániel Antal</span> <span class="authorAux-mtmt"> diszkrét matematika</span>) </a> </span> <span class="author-affil"><span title="Rényi Alfréd Matematikai Kutatóintézet">RAMKI</span>/Diszkrét Matematika</span> </div> </div> <div class="title"><a href="/gui2/?mode=browse&params=publication;33056151" target="_blank">Upper bounds for the necklace folding problems</a></div> <div> <span class="journal-title">JOURNAL OF COMBINATORIAL THEORY SERIES B</span> <span class="journal-issn">(<a target="_blank" href="https://portal.issn.org/resource/ISSN/0095-8956">0095-8956</a> <a target="_blank" href="https://portal.issn.org/resource/ISSN/1096-0902">1096-0902</a>)</span>: <span class="journal-volume">157</span> <span class="page"> pp 123-143 </span> <span class="year">(2022)</span> </div> <div class="pub-footer"> <span class="language" xmlns="http://www.w3.org/1999/html">Nyelv: Angol | </span> <span class="identifiers"> <span class="id identifier oa_GOLD" title=" Gold "> <a style="color:blue" title="10.1016/j.jctb.2022.05.012" target="_blank" href="https://doi.org/10.1016/j.jctb.2022.05.012"> DOI </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="000816900100003" target="_blank" href="https://www.webofscience.com/wos/woscc/full-record/000816900100003"> WoS </a> </span> <span class="id identifier oa_GREEN" title=" Green "> <a style="color:black" title="153735" target="_blank" href="http://real.mtak.hu/153735"> REAL </a> </span> <span class="id identifier oa_GREEN" title=" Green "> <a style="color:black" title="89915" target="_blank" href="https://edit.elte.hu/xmlui/handle/10831/89915"> EDIT </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:black" title="85132553440" target="_blank" href="http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85132553440"> Scopus </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:black" title="2005.12603" target="_blank" href="http://arxiv.org/abs/2005.12603"> arXiv </a> </span> </span> <OnlyViewableByAuthor><div class="ratings"> <div class="journal-subject">Folyóirat szakterülete: Scopus - Computational Theory and Mathematics&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;D1</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Discrete Mathematics and Combinatorics&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;D1</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Theoretical Computer Science&nbsp;&nbsp;&nbsp;SJR indikátor:&nbsp;D1</div> </div></OnlyViewableByAuthor> <div class="publication-citation"> <a target="_blank" href="/api/publication?cond=citations.related;eq;33056151&sort=publishedYear,desc&sort=title"> Idézett közlemények száma: 2 </a> </div> <div class="mtid"><span class="long-pub-mtid">Közlemény: 33056151</span> | <span class="status-data status-ADMIN_APPROVED"> Admin láttamozott </span> Forrás Idéző | <span class="type-subtype">Folyóiratcikk ( Szakcikk ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData">Scopus</span> </div> <div class="lastModified">Utolsó módosítás: 2023.02.10. 16:08 Szabó Regina (ELTE TTK admin 5) </div> <pre class="comment" style="margin-top: 0; margin-bottom: 0;"><u>Megjegyzés</u>: Alfréd Rényi Institute, Budapest, Hungary ELKH–ELTE Geometric and Algebraic Combinatorics Research Group, Budapest, Hungary Department of Computer Science, ELTE Eötvös Loránd University, Budapest, Hungary Export Date: 18 August 2022 CODEN: JCBTB Funding details: ERC-2018-SYG 8...</pre> </div></div>