1
$\begingroup$

Lately there has been a lot of interest on applications of the ham sandwich theorem and related results. There is a bunch of lecture notes and surveys that touch upon the subject. I dont know of any that touches the most recent developments and includes some applications to both combinatorial geometry and functional analysis. Is there a good reference in which they are summarized? The following is a list of the applications that I know of. Do you know of other applications? Heuristically, what is a good principle to recognize problems in which these theorems might lead to a solution?

Applications of the ham sandwich

Alon-Akiyama disjoint rainbows theorem. Alon-West, Goldberg-West. Necklaces for the thieves theorem. Barany-Valtr, Pach. Same type lemma. Matousek, Agarwal-Erickson. Geometric Range Search. Gromov-Milman, Concentration of measure for uniformly convex bodies (localization technique).

Polynomial Ham Sandwhich

Guth's multilinear Kakeya estimate, Guth-Katz: Joints problem, Distinct distances problem. Tao-Solymosi, Matousek-Sharir-Kaplan Generalizations and new proofs of Szemeredi-Trotter, Sum product estimates, Existence of not too selfintersecting geometric tree of Chazelle and Welzl.

Center Point Theorem

Zivaljevic-Vrecica, Dolnikov. The Transversal Center Point Theorem. Thurston-Vavais-Miller-Teng. Separator theorem for planar graphs and for intersection graphs of metric euclidean balls with bounded overlap.

The Yao-Yao partition

Lehec. The Blashke-Santalo functional inequality. Alon-Pach-Radocic-Sharir-Pinchasi Semialgebraic same type lemma for graph-like relations. Fox-Gromov-Naor-Lafforgue-Pach, Bukh-Hubard. Semialgebraic same type lemma.

Convex Equipartitions.

Gromov, Memarian. Tight bounds on the Waist of the sphere for smooth maps. Karasev and Volovikov generalized Gromov's convex equpartitions theorem to obtain a Waist theorem for targets other than $R^k$.

Sorry for the possible mistakes in the pseudocitations.

Improve this question
$\endgroup$
3
  • 8
    $\begingroup$ You should edit your question and flag the "Community Wiki" button. It appears near the bottom of your question once you're in edit mode. It's convention that questions that ask for a list (rather than a definitive answer) are in Community Wiki mode. FYI, there is a book devoted to your question: kam.mff.cuni.cz/~matousek/akt.html Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry (Universitext) [Paperback] Jiri Matousek (Author), A. Björner (Contributor), G.M. Ziegler (Contributor) $\endgroup$
    – Ryan Budney
    Commented Oct 30, 2011 at 17:24
  • 3
    $\begingroup$ "I want a full list"? I want a pony! Wanting to close. $\endgroup$
    – Igor Rivin
    Commented Oct 30, 2011 at 18:07
  • 3
    $\begingroup$ Thanks for the remarks on the wording.Let me know if this is mo material.I think a complete list would be useful for me and others. As for ponies I'm a bit tall to ride them but here is a link with very pretty ones equinenow.com/pony.htm. $\endgroup$
    – Alfredo Hubard
    Commented Oct 30, 2011 at 20:23

1 Answer 1

Reset to default
1
$\begingroup$

The chapter entitled "Topological Methods" by R.T. Živaljević, in the Handbook of Discrete and Computational Geometry, CRC Press, Chapter 14, 2004, is a good source.

I believe ham-sandwich cuts play a role in regression depth computations, e.g., in the 2000 paper by Marshall Bern and David Eppstein, "Multivariate Regression Depth."

Since you consider the center-point theorem and the center-traversal theorem as applications of the ham-sandwich theorem, this leads to a different proof of the Lipton-Tarjan small-separator theorem for planar graphs, a connection established by Miller, Teng, Thurston, and Vavasis in "Separators for sphere-packings and nearest neighbor graphs," Journal of the ACM, 1997.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .