Random necklaces require fewer cuts

DOI10.1137/22M1506699MaRDI QIDQ6386948zbMATH OpenFDO

Authors Noga Alon, Dor Elboim, János Pach, Gábor Tardos

Publication date 29 December 2021

Full work available at URL https://doi.org/10.1137/22M1506699

Mathematics Subject Classification ID

Graph minors (05C83) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

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 $slet$. We show that this probability is polynomially small when $s<(t+1)/2$, it is bounded away from zero when $s>(t+1)/2$, and decays like $Theta(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/logt$, $X(k,t,1)$ is $o(kt)$ with high probability.

Recommendations

• Splitting necklaces
• Necklace bisection with one cut less than needed
• scientific article; zbMATH DE number 496046
• Obstacles for splitting multidimensional necklaces
• Splitting necklaces and measurable colorings of the real line

Cited in

(1)

• Upper bounds for the necklace folding problems

This page was built for publication: Random necklaces require fewer cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6386948)