Namespaces
Variants
Actions

Difference between revisions of "Ham-sandwich theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(also known as the Stone–Tukey theorem)
Line 1: Line 1:
 +
''Stone–Tukey theorem''
 +
 
For any collection of three solids in the three-dimensional space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100601.png" /> there exists a plane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100602.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100603.png" /> measurable sets (mass distributions, finite sets) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100604.png" /> there exists a hyperplane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100605.png" /> simultaneously bisecting all of them.
 
For any collection of three solids in the three-dimensional space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100601.png" /> there exists a plane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100602.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100603.png" /> measurable sets (mass distributions, finite sets) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100604.png" /> there exists a hyperplane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100605.png" /> 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|continuous mapping]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100606.png" /> from a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100607.png" />-dimensional sphere <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100608.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100609.png" />, there exists a pair of antipodal points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h11006010.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h11006011.png" />. (Cf. also [[Antipodes|Antipodes]].)
+
The ham-sandwich theorem is a consequence of the well-known [[Borsuk–Ulam theorem]], which says that for any [[Continuous mapping|continuous mapping]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100606.png" /> from a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100607.png" />-dimensional sphere <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100608.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h1100609.png" />, there exists a pair of antipodal points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h11006010.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110060/h11006011.png" />. (Cf. also [[Antipodes|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.
 
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.

Revision as of 06:24, 28 October 2017

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)
How to Cite This Entry:
Ham-sandwich theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ham-sandwich_theorem&oldid=42200
This article was adapted from an original article by R. Živaljević (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article