Thieves can make sandwiches

DOI10.1112/BLMS.12109zbMATH Open1390.52008arXiv1706.03640OpenAlexW2625269800MaRDI QIDQ4604599FDOQ4604599

Authors: Pavle V. M. Blagojević, Pablo Soberón 

Publication date: 2 March 2018

Published in: Bulletin of the London Mathematical Society (Search for Journal in Brave)

Abstract: We prove a common generalization of the Ham Sandwich theorem and Alon's Necklace Splitting theorem. Our main results show the existence of fair distributions of $m$ measures in $R^d$ among $r$ thieves using roughly $mr/d$ convex pieces, even in the cases when $m$ is larger than the dimension. The main proof relies on a construction of a geometric realization of the topological join of two spaces of partitions of $R^d$ into convex parts, and the computation of the Fadell-Husseini ideal valued index of the resulting spaces.

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

Recommendations

• Splitting multidimensional necklaces
• Balanced convex partitions of measures in \(\mathbb R^{d}\)
• The hamburger theorem
• Splitting necklaces, with constraints
• A ham sandwich theorem for general measures

zbMATH Keywords

convex partitionsAlon's Necklace Splitting theoremFadell-Husseini ideal valued indexHam Sandwich theoremmeasure partition problemtopological join of two spaces

Mathematics Subject Classification ID

Partitions of sets (05A18) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Other problems of combinatorial convexity (52A37) Equivariant operations and obstructions in algebraic topology (55S91)

Cites Work

• Convex equipartitions via equivariant obstruction theory
• A Moment Problem in L 1 Approximation
• An ideal-valued cohomological index theory with applications to Borsuk—Ulam and Bourgin—Yang theorems
• Splitting necklaces
• Splitting multidimensional necklaces
• Convex equipartitions: the spicy chicken theorem
• Bisection of Circle Colorings
• The Early History of the Ham Sandwich Theorem
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Fair Partitioning by Straight Lines
• Equivariant topology of configuration spaces
• Balanced convex partitions of measures in \(\mathbb R^{d}\)
• Fair division and generalizations of Sperner- and KKM-type results
• Measure partitions using hyperplanes with fixed directions

Cited In (7)

• Splitting loops and necklaces: variants of the square peg problem
• Fair division and generalizations of Sperner- and KKM-type results
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• A survey of mass partitions
• Few cuts meet many point sets

This page was built for publication: Thieves can make sandwiches

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