Splitting multidimensional necklaces and measurable colorings of Euclidean spaces

DOI10.1137/130948239zbMATH Open1326.05069arXiv1209.1809OpenAlexW2042852440MaRDI QIDQ3453577FDOQ3453577

Authors: Jarosław Grytczuk, Wojciech Lubawski

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A necklace splitting theorem of Goldberg and West asserts that any k-colored (continuous) necklace can be fairly split using at most k cuts. Motivated by the problem of ErdH{o}s on strongly nonrepetitive sequences, Alon et al. proved that there is a (t+3)-coloring of the real line in which no necklace has a fair splitting using at most t cuts. We generalize this result for higher dimensional spaces. More specifically, we prove that there is k-coloring of R^{d} such that no cube has a fair splitting of size t (using at most t hyperplanes orthogonal to each of the axes), provided k>(t+4)^{d}-(t+3)^{d}+(t+2)^{d}-2^{d}+d(t+2)+3. We also consider a discrete variant of the multidimensional necklace splitting problem in the spirit of the theorem of de Longueville and v{Z}ivaljevi'c. The question how many axes aligned hyperplanes are needed for a fair splitting of a d-dimensional k-colored cube remains open.

Full work available at URL: https://arxiv.org/abs/1209.1809

Recommendations

zbMATH Keywords

Baire theorem discrete necklaces necklace partition

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Exact enumeration problems, generating functions (05A15) Determinants, permanents, traces, other special matrix functions (15A15) Paths and cycles (05C38)

Cited In (4)

This page was built for publication: Splitting multidimensional necklaces and measurable colorings of Euclidean spaces

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