Ham sandwich theorem
In mathematical measure theory, for every positive integer n the ham sandwich theorem states that given n measurable "objects" in n-dimensional Euclidean space, it is possible to divide each one of them in half (with respect to their measure, e.g. volume) with a single (n − 1)-dimensional hyperplane. This is even possible if the objects overlap.
Not to be confused with the squeeze theorem (sometimes called the "sandwich theorem").It was proposed by Hugo Steinhaus and proved by Stefan Banach (explicitly in dimension 3, without taking the trouble to state the theorem in the n-dimensional case), and also years later called the Stone–Tukey theorem after Arthur H. Stone and John Tukey.
History[edit]
According to Beyer & Zardecki (2004), the earliest known paper about the ham sandwich theorem, specifically the n = 3 case of bisecting three solids with a plane, is a 1938 note in a Polish mathematics journal (Editors 1938). Beyer and Zardecki's paper includes a translation of this note, which attributes the posing of the problem to Hugo Steinhaus, and credits Stefan Banach as the first to solve the problem, by a reduction to the Borsuk–Ulam theorem. The note poses the problem in two ways: first, formally, as "Is it always possible to bisect three solids, arbitrarily located, with the aid of an appropriate plane?" and second, informally, as "Can we place a piece of ham under a meat cutter so that meat, bone, and fat are cut in halves?" The note then offers a proof of the theorem.
A more modern reference is Stone & Tukey (1942), which is the basis of the name "Stone–Tukey theorem". This paper proves the n-dimensional version of the theorem in a more general setting involving measures. The paper attributes the n = 3 case to Stanislaw Ulam, based on information from a referee; but Beyer & Zardecki (2004) claim that this is incorrect, given the note mentioned above, although "Ulam did make a fundamental contribution in proposing" the Borsuk–Ulam theorem.
Measure theoretic versions[edit]
In measure theory, Stone & Tukey (1942) proved two more general forms of the ham sandwich theorem. Both versions concern the bisection of n subsets X1, X2, ..., Xn of a common set X, where X has a Carathéodory outer measure and each Xi has finite outer measure.
Their first general formulation is as follows: for any continuous real function , there is a point p of the n-sphere Sn and a real number s0 such that the surface f(p,x) = s0 divides X into f(p,x) < s0 and f(p,x) > s0 of equal measure and simultaneously bisects the outer measure of X1, X2, ..., Xn. The proof is again a reduction to the Borsuk-Ulam theorem. This theorem generalizes the standard ham sandwich theorem by letting f(s,x) = s1x1 + ... + snxn.
Their second formulation is as follows: for any n + 1 measurable functions f0, f1, ..., fn over X that are linearly independent over any subset of X of positive measure, there is a linear combination f = a0f0 + a1f1 + ... + anfn such that the surface f(x) = 0, dividing X into f(x) < 0 and f(x) > 0, simultaneously bisects the outer measure of X1, X2, ..., Xn. This theorem generalizes the standard ham sandwich theorem by letting f0(x) = 1 and letting fi(x), for i > 0, be the i-th coordinate of x.
