Thieves can make sandwiches

DOI10.1112/BLMS.12109MaRDI QIDQ4604599zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(8)

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

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)