×

The hamburger theorem. (English) Zbl 1380.05068

Summary: We generalize the ham sandwich theorem to \(d + 1\) measures on \(\mathbb R^d\) as follows. Let \(\mu_1\), \(\mu_2\),\(\dots\),\(\mu_{d+1}\) be absolutely continuous finite Borel measures on \(\mathbb R^d\). Let \(\omega_i = \mu_i(\mathbb R^d)\) for \(i \in [d + 1]\), \(\omega =\min\{\omega_i;i \in [d + 1]\}\) and assume that \(\sum^{d+1}_{j=1} \omega_j = 1\). Assume that \(\omega_i \leq 1/d\) for every \(i \in [d + 1]\). Then there exists a hyperplane \(h\) such that each open halfspace \(H\) defined by \(h\) satisfies \(\mu_i(H) \leq (\sum^{d+1}_{j=1} \mu_j(H))/d\) for every \(i \in [d + 1]\) and \(\sum^{d+1}_{j=1} \mu_j(H) \geq\min\{1/2, 1 - d\omega\} \geq 1/(d + 1)\). As a consequence we obtain that every \((d + 1)\)-colored set of \(nd\) points in \(\mathbb R^d\) such that no color is used for more than \(n\) points can be partitioned into \(n\) disjoint rainbow \((d - 1)\)-dimensional simplices.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aichholzer, O.; Cabello, S.; Fabila-Monroy, R.; Flores-Peñaloza, D.; Hackl, T.; Huemer, C.; Hurtado, F.; Wood, D., Edge-removal and non-crossing configurations in geometric graphs, Discrete Math. Theor. Comput. Sci., 12, 1, 75-86 (2010) · Zbl 1250.05060
[2] Akiyama, J.; Alon, N., Disjoint simplices and geometric hypergraphs, (Combinatorial Mathematics: Proceedings of the Third International Conference. Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985. Combinatorial Mathematics: Proceedings of the Third International Conference. Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985, Ann. N.Y. Acad. Sci., vol. 555 (1989), New York Acad. Sci.: New York Acad. Sci. New York), 1-3 · Zbl 0734.05064
[3] Beyer, W. A.; Zardecki, A., The early history of the ham sandwich theorem, Am. Math. Mon., 111, 1, 58-61 (2004) · Zbl 1047.55500
[4] Biniaz, A.; Maheshwari, A.; Nandy, S. C.; Smid, M., An optimal algorithm for plane matchings in multipartite geometric graphs, (Algorithms and Data Structures. Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 9214 (2015), Springer), 66-78 · Zbl 1444.68273
[5] Breuer, F., Uneven splitting of ham sandwiches, Discrete Comput. Geom., 43, 4, 876-892 (2010) · Zbl 1197.52005
[6] Cox, G. W.; McKelvey, R. D., A ham sandwich theorem for general measures, Soc. Choice Welf., 1, 1, 75-83 (1984) · Zbl 0555.28001
[7] Elton, J.; Hill, T., A stronger conclusion to the classical ham sandwich theorem, Eur. J. Comb., 32, 5, 657-661 (2011) · Zbl 1228.52015
[8] Hatcher, A., Algebraic Topology (2002), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1044.55001
[9] Hill, T., Common hyperplane medians for random vectors, Am. Math. Mon., 95, 5, 437-441 (1988) · Zbl 0643.60011
[10] Kaneko, A.; Kano, M., Discrete geometry on red and blue points in the plane — a survey, (Discrete and Computational Geometry, Algorithms and Combinatorics, vol. 25 (2003), Springer: Springer Berlin), 551-570 · Zbl 1079.52505
[11] M. Kano, K. Suzuki, personal communication.; M. Kano, K. Suzuki, personal communication.
[12] Kano, M.; Suzuki, K.; Uno, M., Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane, (Discrete and Computational Geometry and Graphs. Discrete and Computational Geometry and Graphs, Lecture Notes in Computer Science, vol. 8845 (2014), Springer), 96-111 · Zbl 1452.05064
[13] Matoušek, J., Using the Borsuk-Ulam theorem, (Lectures on Topological Methods in Combinatorics and Geometry, Written in Cooperation with Anders Björner and Günter M. Ziegler. Lectures on Topological Methods in Combinatorics and Geometry, Written in Cooperation with Anders Björner and Günter M. Ziegler, Universitext (2003), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1016.05001
[14] (Mauldin, R. D., The Scottish Book, Mathematics from the Scottish Café, Including Selected Papers Presented at the Scottish Book Conference Held at North Texas State University. The Scottish Book, Mathematics from the Scottish Café, Including Selected Papers Presented at the Scottish Book Conference Held at North Texas State University, Denton, Tex., May 1979 (1981), Birkhäuser: Birkhäuser Boston, Mass)
[15] Stone, A. H.; Tukey, J. W., Generalized “sandwich” theorems, Duke Math. J., 9, 356-359 (1942) · Zbl 0061.38405
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.