{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:38:28Z","timestamp":1787326708760,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1855464"],"award-info":[{"award-number":["DMS-1855464"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018267"],"award-info":[{"award-number":["2018267"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["GeoScape"],"award-info":[{"award-number":["GeoScape"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003443","name":"Ministry of Education and Science of the Russian Federation","doi-asserted-by":"publisher","award":["075-15-2019-1926"],"award-info":[{"award-number":["075-15-2019-1926"]}],"id":[{"id":"10.13039\/501100003443","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Research, Development and Innovation Office","award":["K-131529"],"award-info":[{"award-number":["K-131529"]}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["Z 342-N31"],"award-info":[{"award-number":["Z 342-N31"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Research, Development and Innovation Office","award":["K-132696"],"award-info":[{"award-number":["K-132696"]}]},{"name":"National Research, Development and Innovation Office","award":["SNN 135643"],"award-info":[{"award-number":["SNN 135643"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>It is known that any open necklace with beads of [Formula: see text] types, in which the number of beads of each type is divisible by [Formula: see text], can be partitioned by at most [Formula: see text] cuts into intervals that can be distributed into [Formula: see text] collections, each containing the same number of beads of each type. This is tight for all values of [Formula: see text] and [Formula: see text]. Here, we consider the case of random necklaces, where the number of beads of each type is [Formula: see text]. Then the minimum number of cuts required for a \u201cfair\u201d partition with the above property is a random variable [Formula: see text]. We prove that for fixed [Formula: see text] and large [Formula: see text], this random variable is at least [Formula: see text] with high probability. For [Formula: see text], fixed [Formula: see text], and large [Formula: see text], we determine the asymptotic behavior of the probability that [Formula: see text] for all values of [Formula: see text]. We show that this probability is polynomially small when [Formula: see text], is bounded away from zero when [Formula: see text], and decays like [Formula: see text] when [Formula: see text]. We also show that for large [Formula: see text], [Formula: see text] is at most [Formula: see text] with high probability and that for large [Formula: see text] and large ratio [Formula: see text], [Formula: see text] is [Formula: see text] with high probability.<\/jats:p>","DOI":"10.1137\/22m1506699","type":"journal-article","created":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T04:47:33Z","timestamp":1714106853000},"page":"1381-1408","source":"Crossref","is-referenced-by-count":0,"title":["Random Necklaces Require Fewer Cuts"],"prefix":"10.1137","volume":"38","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Department of Mathematics, Princeton University, Princeton, NJ 08544 USA, and Schools of Mathematics and Computer Science, Tel Aviv University, Tel Aviv, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3084-4736","authenticated-orcid":true,"given":"Dor","family":"Elboim","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Princeton University, Princeton, NJ 08544 USA, and Schools of Mathematics and Computer Science, Tel Aviv University, Tel Aviv, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[{"name":"Discrete Geometry, R\u00e9nyi Institute, Budapest 1053, Hungary, and MIPT, Moscow, 141701 Russia."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G\u00e1bor","family":"Tardos","sequence":"additional","affiliation":[{"name":"Discrete Geometry, R\u00e9nyi Institute, Budapest 1053, Hungary, and MIPT, Moscow, 141701 Russia."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,4,26]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(87)90055-7"},{"key":"ref2","series-title":"LIPIcs. Leibniz Int. Proc. Inform. 198","first-page":"14","volume-title":"in Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)","author":"Alon N.","year":"2021"},{"key":"ref3","series-title":"Wiley Ser. Discrete Math. Optim.","volume-title":"The Probabilistic Method","author":"Alon N.","year":"2016","edition":"4"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.12.003"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1952-0045327-5"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"A. Dvoretzky and P. Erd\u0151s, Some problems on random walk in space, in Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950, University of California Press, Berkeley-Los Angeles, CA, 1951, pp. 353\u2013367.","DOI":"10.1525\/9780520411586-026"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020942"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020631"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"A. Filos-Ratsikas and P. W. Goldberg, The complexity of splitting necklaces and bisecting ham sandwiches, in Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), 2019, pp. 638\u2013649.","DOI":"10.1145\/3313276.3316334"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.01.030"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01214889"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01221219"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90074-5"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100010860"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100010112"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01458701"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.3150\/18-BEJ1072"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1142\/8678"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00605-019-01316-3"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1506699","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:35:01Z","timestamp":1787322901000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1506699"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,26]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1137\/22M1506699"],"URL":"https:\/\/doi.org\/10.1137\/22m1506699","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,26]]}}}