Ham-sandwich theorem

Stone–Tukey theorem

For any collection of three solids in the three-dimensional space $ \mathbf R ^ {3} $ there exists a plane $ L $ which simultaneously bisects all of them, i.e. divides each of the solids into two halfs of equal volume. In a popular form this result is stated as the fact that it is possible to cut fairly an open ham-sandwich consisting of two pieces of bread and a piece of ham with a single straight cut. More generally, for a collection of $ d $ measurable sets (mass distributions, finite sets) in $ \mathbf R ^ {d} $ there exists a hyperplane $ H $ simultaneously bisecting all of them.

The ham-sandwich theorem is a consequence of the well-known Borsuk–Ulam theorem, which says that for any continuous mapping $ f : {S ^ {d} } \rightarrow {\mathbf R ^ {d} } $ from a $ d $- dimensional sphere $ S ^ {d} $ into $ \mathbf R ^ {d} $, there exists a pair of antipodal points $ \{ v, - v \} \subset S ^ {d} $ such that $ f ( - v ) = f ( v ) $. (Cf. also Antipodes.)

Other examples of combinatorial partitions of masses include the "centre-point theorem" and the related "centre-transversal theorem" , equi-partitions of masses by higher-dimensional "orthants" , equi-partitions by convex cones, partitions of lines and other geometric objects, etc.

The centre-point theorem says that for any measurable set in $ A \subset \mathbf R ^ {d} $ there exists a point $ x \in \mathbf R ^ {d} $ such that for any half-space $ P \subset \mathbf R ^ {d} $: if $ x \in P $ then

$$ { \mathop{\rm vol} } ( P \cap A ) \geq { \frac{1}{d + 1 } } { \mathop{\rm vol} } ( A ) . $$

The centre-transversal theorem, [a5], is a generalization of both the ham-sandwich and the centre-point theorem and it claims that for any collection $ A _ {0} \dots A _ {k} $, $ 0 \leq k \leq d - 1 $, of Lebesgue-measurable sets in $ \mathbf R ^ {d} $( cf. also Lebesgue measure) there exists a $ k $- dimensional affine subspace $ D \subset \mathbf R ^ {d} $ such that for every closed half-space $ P $ and every $ i $: if $ D \subset P $ then

$$ \mu ( A _ {i} \cap P ) \geq { \frac{1}{d - k + 1 } } \mu ( A _ {i} ) . $$

An example of an equi-partition result into higher-dimensional "orthants" is as follows, [a3]. Any measurable set $ A \subset \mathbf R ^ {5} $ can be partitioned into $ 16 $ pieces of equal measure by $ 4 $ hyperplanes.

The proofs of all these and other related results are topological and use several forms of generalized Borsuk–Ulam-type theorems, see [a2], [a4], [a6].

The ham-sandwich theorem, together with other relatives belonging to combinatorial (equi)partitions of masses, has been often applied to problems of discrete and computational geometry, see [a5] for a survey.

See also Comitant.

References

[a1]	A. Björner, "Topological methods" R. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , North-Holland (1995)
[a2]	E. Fadell, S. Husseini, "An ideal-valued cohomological index theory with applications to Borsuk–Ulam and Bourgin–Yang theorems" Ergod. Th. & Dynam. Sys. , 8 (1988) pp. 73–85
[a3]	E. Ramos, "Equipartitions of mass distributions, by hyperplanes" Discr. Comp. Geometry , 15 (1996) pp. 147-167
[a4]	H. Steinlein, "Borsuk's antipodal theorem and its generalizations, and applications: a survey" , Topological Methods in Nonlinear Analysis , Sém. Math. Sup. , 95 , Presses Univ. Montréal (1985) pp. 166–235
[a5]	R.T. Živaljević, "Topological methods" J.E. Goodman (ed.) J. O'Rourke (ed.) , CRC Handbook of Discrete and Combinatorial Geometry , CRC Press (1997)
[a6]	R.T. Živaljević, "User's guide to equivariant methods in combinatorics" Publ. Inst. Math. Belgrade , 59 (73) (1996)