Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Obstacles for splitting multidimensional necklaces
HTML articles powered by AMS MathViewer

by Michał Lasoń PDF
Proc. Amer. Math. Soc. 143 (2015), 4655-4668 Request permission

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
Similar Articles
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
  • 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
  • © Copyright 2015 American Mathematical Society
  • 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
  • MathSciNet review: 3391025