Topology and combinatorics of partitions of masses by hyperplanes. (English) Zbl 1110.68155
Summary: An old problem in combinatorial geometry is to determine when one or more measurable sets in \(\mathbb R^d\) admit an equipartition by a collection of \(k\) hyperplanes [B. Grünbaum, Pac. J. Math. 10, 1257–1261 (1960; Zbl 0101.14603)]. A related topological problem is the question of (non)existence of a map \(f:(S^d)^k \to S(U)\), equivariant with respect to the Weyl group \(W_k = B_k := (\mathbb Z/2)^{\oplus k} \rtimes S_k\), where \(U\) is a representation of \(W_k\) and \(S(U) \subset U\) the corresponding unit sphere. We develop general methods for computing topological obstructions for the existence of such equivariant maps. Among the new results is the well-known open case of 5 measures and 2 hyperplanes in \(\mathbb R^8\) [E. A. Ramos, Discrete Comput. Geom. 15, 147–167 (1996; Zbl 0843.68120)]. The obstruction in this case is identified as the element \(2X_{ab} \in H_1 (\mathbb D_8; \mathcal Z) \cong \mathbb Z/4\), where \(X_{ab}\) is a generator, which explains why this result cannot be obtained by the parity count formulas of Ramos [loc. cit.] or the methods based on either Stiefel-Whitney classes or ideal valued cohomological index theory [E. Fadell and S. Husseini, Ergodic Theory Dynam. Syst. 8, 73–85 (1988; Zbl 0657.55002)].
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 55M20 | Fixed points and coincidences in algebraic topology |
Keywords:
equipartitions of masses; equivariant maps; cyclic words; obstruction theory; cohomological index theoryReferences:
| [1] | Agarwal, P. K., Range searching, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (2004), Chapman & Hall/CRC), (Chapter 36) · Zbl 0806.68106 |
| [2] | Aigner, M., Combinatorial Theory (1979), Springer: Springer Berlin · Zbl 0415.05001 |
| [3] | Athanasiadis, C. A.; Rambau, J.; Santos, F., The generalized Baues problem for cyclic polytopes II, Publ. Inst. Math., 66, 80, 3-15 (1999) · Zbl 1009.52023 |
| [4] | Alon, N., Splitting necklaces, Adv. Math., 63, 247-253 (1987) · Zbl 0635.05008 |
| [5] | Alon, N., Some recent combinatorial applications of Borsuk-type theorems, (Deza, M. M.; Frankl, P.; Rosenberg, D. G., Algebraic, Extremal and Metric Combinatorics (1988), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 1-12 · Zbl 0679.05054 |
| [6] | Bárány, I., Geometric and combinatorial applications of Borsuk’s theorem, (Pach, J., New Trends in Discrete and Computational Geometry. New Trends in Discrete and Computational Geometry, Algorithms and Combinatorics, vol. 10 (1993), Springer: Springer Berlin) · Zbl 0788.52012 |
| [7] | Bárány, I.; Matoušek, J., Simultaneous partitions of measures by \(k\)-fans, Discrete Comput. Geom., 25, 3, 317-334 (2001) · Zbl 0989.52009 |
| [8] | Billingsley, P., Convergence of Probability Measures (1968), John Wiley & Sons · Zbl 0172.21201 |
| [9] | Björner, A., Topological methods, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), North-Holland: North-Holland Amsterdam) · Zbl 0851.52016 |
| [10] | Borsuk, K., Drei Sätze über die \(n\)-dimensionale euklidische Sphäre, Fund. Math., 20, 177-190 (1933) · JFM 59.0560.01 |
| [11] | Brown, K. S., Cohomology of Groups (1982), Springer · Zbl 0367.18012 |
| [12] | Conner, P. E.; Floyd, E. E., Differentiable Periodic Maps, Ergeb. Math. Grenzgeb. (Neue Folge), vol. 33 (1964), Springer · Zbl 0125.40103 |
| [13] | tom Dieck, T., Transformation Groups, de Gruyter Stud. Math., vol. 8 (1987), Springer: Springer Berlin · Zbl 0611.57002 |
| [14] | Dold, A., Parametrized Borsuk-Ulam theorems, Comment. Math. Helv., 63, 275-285 (1988) · Zbl 0651.55002 |
| [15] | Eckhoff, J., Helly, Radon and Carathéodory type theorems, (Gruber, P. M.; Wills, J. M., Handbook of Convex Geometry (1993), North-Holland: North-Holland Amsterdam), 389-448 · Zbl 0791.52009 |
| [16] | Fadell, E.; Husseini, S., Index theory for \(G\)-bundle pairs with applications to Borsuk-Ulam type theorems for \(G\)-sphere bundles, (Nonlinear Analysis (1987), World Scientific: World Scientific Singapore), 307-337 · Zbl 0676.55019 |
| [17] | Fadell, E.; Husseini, S., An ideal-valued cohomological index theory with applications to Borsuk-Ulam and Bourgin-Yang theorems, Ergodic Theory Dynam. Systems, \(8^*, 73-85 (1988)\) · Zbl 0657.55002 |
| [18] | Gessel, I. M.; Stanley, R. P., Algebraic enumeration, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), North-Holland: North-Holland Amsterdam) · Zbl 0853.05002 |
| [19] | Grünbaum, B., Partitions of mass-distributions and convex bodies by hyperplanes, Pacific J. Math., 10, 1257-1261 (1960) · Zbl 0101.14603 |
| [20] | Hadwiger, H., Simultane Vierteilung zweier Körper, Arch. Math. (Basel), 17, 274-278 (1966) · Zbl 0137.41501 |
| [21] | Izydorek, M.; Rybicki, S., On parametrized Borsuk-Ulam theorem for free \(Z_p\)-action, (Proc. Barcelona Conf. on Alg. Topology 1990. Proc. Barcelona Conf. on Alg. Topology 1990, Lecture Notes in Math., vol. 1509 (1992), Springer), 227-234 · Zbl 0755.55001 |
| [22] | Jaworowski, J., A continuous version of the Borsuk-Ulam theorem, Proc. Amer. Math. Soc., 82, 112-114 (1981) · Zbl 0469.55003 |
| [23] | Krishnamurthy, V., Combinatorics, Theory and Applications (1985), East-West Press · Zbl 0584.05001 |
| [24] | Lovász, L., Kneser’s conjecture, chromatic number and homotopy, J. Combin. Theory Ser. A, 25, 319-324 (1978) · Zbl 0418.05028 |
| [25] | Makeev, V. V., On some combinatorial geometric problems on vector bundles, Algebra i Analiz, 14, 169-191 (2002), (in Russian) · Zbl 1037.52010 |
| [26] | Matoušek, J., Efficient partition trees, Discrete Comput. Geom., 8, 315-334 (1992) · Zbl 0752.68088 |
| [27] | Matoušek, J., Range searching with efficient hierarchical cuttings, Discrete Comput. Geom., 10, 157-182 (1993) · Zbl 0774.68101 |
| [28] | J. Matoušek, Geometric range searching, Report B 93-09, Institute for Computer Science, Department of Mathematics, Freie Universität, Berlin, July 1993; J. Matoušek, Geometric range searching, Report B 93-09, Institute for Computer Science, Department of Mathematics, Freie Universität, Berlin, July 1993 |
| [29] | Matoušek, J., Using the Borsuk-Ulam Theorem, Lectures on Topological Methods in Combinatorics and Geometry (2003), Springer · Zbl 1016.05001 |
| [30] | (Pach, J., New Trends in Discrete and Computational Geometry. New Trends in Discrete and Computational Geometry, Algorithms and Combinatorics, vol. 10 (1993), Springer) · Zbl 0773.00009 |
| [31] | Rado, R., A theorem on general measure, J. London Math. Soc., 26, 291-300 (1946) · Zbl 0061.09606 |
| [32] | Ramos, E. A., Equipartitions of mass distributions by hyperplanes, Discrete Comput. Geom., 15, 147-167 (1996) · Zbl 0843.68120 |
| [33] | Stanley, R. P., Enumerative Combinatorics, vols. 1, 2 (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge: Cambridge Univ. Press: Cambridge Univ. Press: Cambridge Univ. Press Cambridge: Cambridge Univ. Press Cambridge · Zbl 0928.05001 |
| [34] | Tverberg, H.; Vrećica, S., On generalizations of Radon’s theorem and the ham sandwich theorem, European J. Combin., 14, 259-264 (1993) · Zbl 0777.52005 |
| [35] | Vrećica, S., Tverberg’s conjecture, Discrete Comput. Geom., 29, 4, 505-510 (2003) · Zbl 1069.52009 |
| [36] | Vrećica, S.; Živaljević, R., The ham-sandwich theorem revisited, Israel J. Math., 78, 21-32 (1992) · Zbl 0777.57011 |
| [37] | Vrećica, S.; Živaljević, R., New cases of the colored Tverberg theorem, (Barcelo, H.; Kalai, G., Jerusalem Combinatorics ’93. Jerusalem Combinatorics ’93, Contemp. Math. (1994), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI) · Zbl 0824.52010 |
| [38] | Vrećica, S.; Živaljević, R., Conical equipartitions of mass distributions, Discrete Comput. Geom., 25, 335-350 (2001) · Zbl 0989.52010 |
| [39] | Wall, C. T.C., Surgery on Compact Manifolds, Math. Surveys Monogr., vol. 69 (1999), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI · Zbl 0935.57003 |
| [40] | Willard, D. E., Polygon retrieval, SIAM J. Comput., 11, 149-165 (1982) · Zbl 0478.68060 |
| [41] | Wilkerson, C., A primer on the Dickson invariants, (Proceedings of the Northwestern Homotopy Theory Conference. Proceedings of the Northwestern Homotopy Theory Conference, Contemp. Math., vol. 19 (1983)), 421-434 · Zbl 0525.55013 |
| [42] | Yao, F.; Dobkin, D.; Edelsbrunner, H.; Paterson, M., Partitioning space for range queries, SIAM J. Comput., 18, 371-384 (1989) · Zbl 0675.68066 |
| [43] | Yao, A. C.; Yao, F. F., A general approach to \(d\)-dimensional geometric queries, (Proceedings of the 17th ACM Annual Symposium on the Theory of Computing (1985), ACM), 163-169 |
| [44] | Ziegler, G. M., Lectures on Polytopes, Grad. Texts in Math. (1995), Springer · Zbl 0823.52002 |
| [45] | Živaljević, R., User’s guide to equivariant methods in combinatorics, Publ. Inst. Math. Belgrade, 59, 73, 114-130 (1996) · Zbl 0946.52001 |
| [46] | Živaljević, R., Combinatorics of topological posets: Homotopy complementation formulas, Adv. in Appl. Math., 21, 547-574 (1998) · Zbl 0917.06003 |
| [47] | Živaljević, R., User’s guide to equivariant methods in combinatorics II, Publ. Inst. Math. Belgrade, 64, 78, 107-132 (1998) · Zbl 0999.52005 |
| [48] | Živaljević, R., The Tverberg-Vrećica problem and the combinatorial geometry on vector bundles, Israel J. Math., 111, 53-76 (1999) · Zbl 0972.52005 |
| [49] | Živaljević, R., Topological methods, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (2004), Chapman & Hall/CRC), (Chapter 14) · Zbl 0955.52500 |
| [50] | Živaljević, R.; Vrećica, S., An extension of the ham sandwich theorem, Bull. London Math. Soc., 22, 183-186 (1990) · Zbl 0709.60011 |
| [51] | Živaljević, R.; Vrećica, S., The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A, 61, 2, 309-318 (1992) · Zbl 0782.52003 |
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.
