Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 
 

 

Obstacles for splitting multidimensional necklaces


Author: Michał\ Lasoń
Journal: Proc. Amer. Math. Soc. 143 (2015), 4655-4668
MSC (2010): Primary 05D99, 54H99, 12E99, 52C45
DOI: https://doi.org/10.1090/S0002-9939-2015-12611-1
Published electronically: April 1, 2015
MathSciNet review: 3391025
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The well-known ``necklace splitting theorem'' of Alon (1987) asserts that every $ k$-colored necklace can be fairly split into $ q$ parts using at most $ t$ cuts, provided $ k(q-1)\leq t$. In a joint paper with Alon et al. (2009) we studied a kind of opposite question. Namely, for which values of $ k$ and $ t$ is there a measurable $ k$-coloring of the real line such that no interval has a fair splitting into $ 2$ parts with at most $ t$ cuts? We proved that $ k>t+2$ is a sufficient condition (while $ k>t$ is necessary).

We generalize this result to Euclidean spaces of arbitrary dimension $ d$, and to arbitrary number of parts $ q$. We prove that if $ k(q-1)>t+d+q-1$, then there is a measurable $ k$-coloring of $ \mathbb{R}^d$ such that no axis-aligned cube has a fair $ q$-splitting using at most $ t$ axis-aligned hyperplane cuts. Our bound is of the same order as a necessary condition $ k(q-1)>t$ implied by Alon's 1987 work. Moreover, for $ d=1,q=2$ we get exactly the result of the 2009 work.

Additionally, we prove that if a stronger inequality $ k(q-1)>dt+d+q-1$ is satisfied, then there is a measurable $ k$-coloring of $ \mathbb{R}^d$ with no axis-aligned cube having a fair $ q$-splitting using at most $ t$ arbitrary hyperplane cuts. The proofs are based on the topological Baire category theorem and use algebraic independence over suitably chosen fields.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05D99, 54H99, 12E99, 52C45

Retrieve articles in all journals with MSC (2010): 05D99, 54H99, 12E99, 52C45


Additional Information

Michał\ Lasoń
Affiliation: École Polytechnique Fédérale de Lausanne, Chair of Combinatorial Geometry, EPFL-SB-MATHGEOM/DCG, Station 8, CH-1015 Lausanne, Switzerland; and Institute of Mathematics of the Polish Academy of Sciences, ul.Śniadeckich 8, 00-656 Warszawa, Poland
Email: michalason@gmail.com

DOI: https://doi.org/10.1090/S0002-9939-2015-12611-1
Keywords: Necklace splitting, multidimensional necklace, measurable coloring, mass equipartition
Received by editor(s): November 13, 2013
Received by editor(s) in revised form: August 8, 2014
Published electronically: April 1, 2015
Additional Notes: This research was supported by Polish National Science Centre grant no. 2012/05/D/ST1/01063 and by Swiss National Science Foundation Grants 200020-144531 and 200021-137574.
Communicated by: Jim Haglund
Article copyright: © Copyright 2015 American Mathematical Society