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
- Noga Alon and Douglas B. West, The Borsuk-Ulam theorem and bisection of necklaces, Proc. Amer. Math. Soc. 98 (1986), no. 4, 623–628. MR 861764, DOI 10.1090/S0002-9939-1986-0861764-9
- Noga Alon, Splitting necklaces, Adv. in Math. 63 (1987), no. 3, 247–253. MR 877785, DOI 10.1016/0001-8708(87)90055-7
- Noga Alon, Jarosław Grytczuk, MichałLasoń, and Mateusz Michałek, Splitting necklaces and measurable colorings of the real line, Proc. Amer. Math. Soc. 137 (2009), no. 5, 1593–1599. MR 2470817, DOI 10.1090/S0002-9939-08-09699-8
- Pavle V. M. Blagojević and Günter M. Ziegler, The ideal-valued index for a dihedral group action, and mass partition by two hyperplanes, Topology Appl. 158 (2011), no. 12, 1326–1351. MR 2812486, DOI 10.1016/j.topol.2011.05.008
- Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271, DOI 10.1007/978-3-642-61568-9
- Charles H. Goldberg and Douglas B. West, Bisection of circle colorings, SIAM J. Algebraic Discrete Methods 6 (1985), no. 1, 93–106. MR 772181, DOI 10.1137/0606010
- Jarosław Grytczuk and Wojciech Lubawski, Splitting multidimensional necklaces and measurable colorings of Euclidean spaces, SIAM J. Discrete Math. 29 (2015), no. 1, 252–258. MR 3304259, DOI 10.1137/130948239
- Jarosław Grytczuk and Wiesław Śliwa, Non-repetitive colorings of infinite sets, Discrete Math. 265 (2003), no. 1-3, 365–373. MR 1969386, DOI 10.1016/S0012-365X(02)00879-8
- Charles R. Hobby and John R. Rice, A moment problem in $L_{1}$ approximation, Proc. Amer. Math. Soc. 16 (1965), 665–670. MR 178292, DOI 10.1090/S0002-9939-1965-0178292-5
- Mark de Longueville and Rade T. Živaljević, Splitting multidimensional necklaces, Adv. Math. 218 (2008), no. 3, 926–939. MR 2414326, DOI 10.1016/j.aim.2008.02.003
- Peter Mani-Levitska, Siniša Vrećica, and Rade Živaljević, Topology and combinatorics of partitions of masses by hyperplanes, Adv. Math. 207 (2006), no. 1, 266–296. MR 2264074, DOI 10.1016/j.aim.2005.11.013
- Jiří Matoušek, Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry; Written in cooperation with Anders Björner and Günter M. Ziegler. MR 1988723
- Benjamin Matschke, A note on mass partitions by hyperplanes, arXiv 1001.0193.
- John C. Oxtoby, Measure and category, 2nd ed., Graduate Texts in Mathematics, vol. 2, Springer-Verlag, New York-Berlin, 1980. A survey of the analogies between topological and measure spaces. MR 584443
- E. A. Ramos, Equipartition of mass distributions by hyperplanes, Discrete Comput. Geom. 15 (1996), no. 2, 147–167. MR 1368272, DOI 10.1007/BF02717729
- Siniša Vrećica and Rade Živaljević, Measurable patterns, necklaces, and sets indiscernible by measure, arXiv:1305.7474.
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