Alon, N. and Elboim, D. and Pach, János and Tardos, Gábor (2024) Random Necklaces Require Fewer Cuts. SIAM JOURNAL ON DISCRETE MATHEMATICS, 38 (2). pp. 1381-1408. ISSN 0895-4801
|
Text
2112.14488v1.pdf Download (307kB) | Preview |
Abstract
It is known that any open necklace with beads of t types, in which the number of beads of each type is divisible by k, can be partitioned by at most (k 1)t cuts into intervals that can be distributed into k collections, each containing the same number of beads of each type. This is tight for all values of k and t. Here, we consider the case of random necklaces, where the number of beads of each type is km. Then the minimum number of cuts required for a "fair"partition with the above property is a random variable X(k, t,m). We prove that for fixed k, t and large m, this random variable is at least (k 1)(t + 1)/2 with high probability. For k = 2, fixed t, and large m, we determine the asymptotic behavior of the probability that X(2, t,m) = s for all values of s ≤ t. We show that this probability is polynomially small when s < (t + 1)/2, is bounded away from zero when s > (t + 1)/2, and decays like Θ (1/ logm) when s = (t + 1)/2. We also show that for large t, X(2, t, 1) is at most (0.4 + o(1))t with high probability and that for large t and large ratio k/ log t, X(k, t, 1) is o(kt) with high probability. © 2024 SIAM.
| Item Type: | Article |
|---|---|
| Additional Information: | Export Date: 20 September 2024 CODEN: SJDME Funding details: Engineering Research Centers, ERC Funding details: United States-Israel Binational Science Foundation, BSF Funding details: European Research Council, ERC Funding details: Austrian Science Fund, FWF, Z 342-N31, SNN 135643, K-132696 Funding details: Austrian Science Fund, FWF Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, K-131529 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH Funding details: National Science Foundation, NSF, DMS-1855464 Funding details: National Science Foundation, NSF Funding details: 075-15-2019-1926 Funding details: Bloom's Syndrome Foundation, BSF, 2018267 Funding details: Bloom's Syndrome Foundation, BSF Funding text 1: \\\\ast Received by the editors June 30, 2022; accepted for publication (in revised form) January 9, 2024; published electronically April 26, 2024. https://doi.org/10.1137/22M1506699 Funding: The work of the first author was partially supported by National Science Foundation (NSF) grant DMS-1855464 and Binational Science Foundation (BSF) grant 2018267. The work of the third and fourth authors was supported by European Research Council (ERC) Advanced Grant ``GeoScape"" and Russian Federation Megagrant 075-15-2019-1926. The third author was also supported by National Research, Development and Innovation Office (NKFIH) grant K-131529 and Austrian Science Fund (FWF) grant Z 342-N31. The fourth author was also supported by NKFIH grants K-132696 and SNN 135643. |
| Uncontrolled Keywords: | PROPERTY; asymptotic behaviour; Method of moments; Random variables; Random walk; Random walk; High probability; second moment method; Necklace; Necklace; Second moment methods; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 31 Dec 2024 05:28 |
| Last Modified: | 31 Dec 2024 05:28 |
| URI: | https://real.mtak.hu/id/eprint/212575 |
Actions (login required)
 |
Edit Item |
