Ham-sandwich theorem

Stone–Tukey theorem

For any collection of three solids in the three-dimensional space there exists a plane 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 measurable sets (mass distributions, finite sets) in there exists a hyperplane 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 from a -dimensional sphere into , there exists a pair of antipodal points such that . (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 there exists a point such that for any half-space : if then

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 , , of Lebesgue-measurable sets in (cf. also Lebesgue measure) there exists a -dimensional affine subspace such that for every closed half-space and every : if then

An example of an equi-partition result into higher-dimensional "orthants" is as follows, [a3]. Any measurable set can be partitioned into pieces of equal measure by 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)