Abstract
The BorsukUlam theorem is a fundamental result in algebraic topology, with applications to various areas of Mathematics. A classical application of the BorsukUlam theorem is the Ham Sandwich theorem: The volumes of any n compact sets in R^n can always be simultaneously bisected by an (n1)dimensional hyperplane.
In this paper, we demonstrate the equivalence between the BorsukUlam theorem and the Ham Sandwich theorem. The main technical result we show towards establishing the equivalence is the following: For every odd polynomial restricted to the hypersphere f:S^n>R, there exists a compact set A in R^{n+1}, such that for every x in S^n we have f(x)=vol(A cap H^+)  vol(A cap H^), where H is the oriented hyperplane containing the origin with x as the normal. A noteworthy aspect of the proof of the above result is the use of hyperspherical harmonics.
Finally, using the above result we prove that there exist constants n_0, epsilon_0>0 such that for every n>= n_0 and epsilon <= epsilon_0/sqrt{48n}, any query algorithm to find an epsilonbisecting (n1)dimensional hyperplane of n compact set in [n^4.51,n^4.51]^n, even with success probability 2^Omega(n), requires 2^Omega(n) queries.
BibTeX  Entry
@InProceedings{cs_et_al:LIPIcs:2017:7232,
author = {Karthik C. S. and Arpan Saha},
title = {{Ham Sandwich is Equivalent to BorsukUlam}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {24:124:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7232},
URN = {urn:nbn:de:0030drops72325},
doi = {10.4230/LIPIcs.SoCG.2017.24},
annote = {Keywords: Ham Sandwich theorem, BorsukUlam theorem, Query Complexity, Hyperspherical Harmonics}
}
Keywords: 

Ham Sandwich theorem, BorsukUlam theorem, Query Complexity, Hyperspherical Harmonics 
Collection: 

33rd International Symposium on Computational Geometry (SoCG 2017) 
Issue Date: 

2017 
Date of publication: 

20.06.2017 