Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Regular Polygonal Partitions of a Tverberg Type

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

A seminal theorem of Tverberg states that any set of \(T(r,d)=(r-1)(d+1)+1\) points in \({\mathbb {R}}^{d}\) can be partitioned into r subsets whose convex hulls have non-empty r-fold intersection. Almost any collection of fewer points in \({\mathbb {R}}^{d}\) cannot be so divided, and in these cases we ask if the set can nonetheless be P(r, d)-partitioned, i.e., split into r subsets so that there exist r points, one from each resulting convex hull, which form the vertex set of a prescribed convex d-polytope P(r, d). Our main theorem shows that this is the case for any generic \(T(r,2)-2\) points in the plane and any \(r\ge 3\) when \(P(r,2)=P_{r}\) is a regular r-gon, and moreover that \(T(r,2)-2\) is tight. For higher dimensional polytopes and \(r=r_{1}\cdots r_{k}\), \(r_{i} \ge 3\), this generalizes to \(T(r,2k)-2k\) generic points in \({\mathbb {R}}^{2k}\) and orthogonal products \(P(r,2k)=P_{r_{1}}\times \cdots \times P_{r_{k}}\) of regular polygons, and likewise to \(T(2r,2k+1)-(2k+1)\) points in \({\mathbb {R}}^{2k+1}\) and the product polytopes \(P(2r,2k+1)=P_{r_{1}}\times \cdots \times P_{r_{k}}\times P_{2}\). As with Tverberg’s original theorem, our results admit topological generalizations when r is a prime power, and, using the “constraint method” of Blagojević, Frick, and Ziegler, allow for dimensionally restricted versions of a van Kampen–Flores type and colored analogues in the fashion of Soberón.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Asada, M., Chen, R., Frick, F., Huang, F., Polevy, M., Stoner, D., Tsang, L.H., Wellner, Z.: On Reay’s relaxed Tverberg conjecture and generalizations of Conway’s thrackle conjecture. Electron. J. Combin. 25(3), # 3.16 (2018)

  2. Bárány, I.: A generalization of Carathéodory’s theorem. Discrete Math. 40(2–3), 141–152 (1982)

    Article  MathSciNet  Google Scholar 

  3. Bárány, I., Larman, D.G.: A colored version of Tverberg’s theorem. J. Lond. Math. Soc. 45(2), 314–320 (1992)

    Article  MathSciNet  Google Scholar 

  4. Bárány, I., Shlosman, S.B., Szűcs, A.: On a topological generalization of a theorem of Tverberg. J. Lond. Math. Soc. 23(1), 158–164 (1981)

    Article  MathSciNet  Google Scholar 

  5. Bárány, I., Soberón, P.: Tverberg’s theorem is 50 years old: a survey. Bull. Am. Math. Soc. 55(4), 459–492 (2018)

    Article  MathSciNet  Google Scholar 

  6. Blagojević, P.V.M., Frick, F., Ziegler, G.M.: Tverberg plus constraints. Bull. Lond. Math. Soc. 46(5), 953–967 (2014)

    Article  MathSciNet  Google Scholar 

  7. Blagojević, P.V.M., Frick, F., Ziegler, G.M.: Barycenters of polytope skeleta and counterexamples to the topological Tverberg conjecture, via constraints. J. Eur. Math. Soc. 21(7), 2107–2116 (2019)

    Article  MathSciNet  Google Scholar 

  8. Blagojević, P.V.M., Matschke, B., Ziegler, G.M.: Optimal bounds for the colored Tverberg problem. J. Eur. Math. Soc. 17(4), 739–754 (2015)

    Article  MathSciNet  Google Scholar 

  9. Blagojević, P.V.M., Ziegler, G.M.: Beyond the Borsuk–Ulam theorem: the topological Tverberg story. In: A Journey Through Discrete Mathematics, pp. 273–341. Springer, Cham (2017)

  10. De Loera, J.A., Goaoc, X., Meunier, F., Mustafa, N.H.: The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. Bull. Am. Math. Soc. 56(3), 415–511 (2019)

    Article  Google Scholar 

  11. Flores, A.: Über \(n\)-dimensionale Komplexe, die im \(R_{2n+1}\) absolut selbstverschlungen sind. Erg. Math. Kolloqu. 6, 4–7 (1935)

    MATH  Google Scholar 

  12. Frick, F.: Counterexamples to the topological Tverberg conjecture. Oberwolfach Rep. 11(1), 34–37 (2014)

    Google Scholar 

  13. Gromov, M.: Singularities, expanders and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal. 20(2), 416–526 (2010)

    Article  MathSciNet  Google Scholar 

  14. van Kampen, E.R.: Komplexe in euklidischen Räumen. Abh. Math. Sem. Univ. Hamburg 9(1), 72–78 (1933)

    Article  MathSciNet  Google Scholar 

  15. Mabillard, I., Wagner, U.: Eliminating Tverberg points, I. An analogue of the Whitney trick. In: 30th Annual Symposium on Computational Geometry (Kyoto 2014), pp. 171–180. ACM, New York (2014)

  16. Matschke, B.: A survey on the square peg problem. Not. Am. Math. Soc. 61(4), 346–352 (2014)

    Article  MathSciNet  Google Scholar 

  17. Meyerson, M.D.: Balancing acts. Topol. Proc. 6(1), 59–75 (1981)

    MathSciNet  MATH  Google Scholar 

  18. Nielsen, M.J.: Triangles inscribed in simple closed curves. Geom. Dedicata 43(3), 291–297 (1992)

    Article  MathSciNet  Google Scholar 

  19. Özaydin, M.: Equivariant maps for the symmetric group (1987). http://digital.library.wisc.edu/1793/63829

  20. Perles, M.A., Sigron, M.: Some variations on Tverberg’s theorem. Isr. J. Math. 216(2), 957–972 (2016)

    Article  MathSciNet  Google Scholar 

  21. Reay, J.R.: Several generalizations of Tverberg’s theorem. Isr. J. Math. 34(3), 238–244 (1979)

    Article  MathSciNet  Google Scholar 

  22. Sarkaria, K.S.: A generalized van Kampen–Flores theorem. Proc. Am. Math. Soc. 111(2), 559–565 (1991)

    Article  MathSciNet  Google Scholar 

  23. Sarkaria, K.S.: Tverberg partitions and Borsuk–Ulam theorems. Pac. J. Math. 196(1), 231–241 (2000)

    Article  MathSciNet  Google Scholar 

  24. Serre, J.-P.: Linear Representations of Finite Groups. Graduate Texts in Mathematics, vol. 42. Springer, New York (1977)

  25. Simon, S.: Average-value Tverberg partitions via finite Fourier analysis. Isr. J. Math. 216(2), 891–904 (2016)

    Article  MathSciNet  Google Scholar 

  26. Soberón, P.: Equal coefficients and tolerance in coloured Tverberg partitions. Combinatorica 35(2), 235–252 (2015)

    Article  MathSciNet  Google Scholar 

  27. Toeplitz, O.: Ueber einige Aufgaben der Analysis situs. Verhandlungen der Schweizerischen Naturforschenden Gesellschaft in Solothurn 4, 197 (1911)

    Google Scholar 

  28. Tverberg, H.: A generalization of Radon’s theorem. J. Lond. Math. Soc. 41, 123–128 (1966)

    Article  MathSciNet  Google Scholar 

  29. Volovikov, A.Yu.: On a topological generalization of the Tverberg theorem. Math. Notes 59(3), 324–326 (1996)

  30. Volovikov, A.Yu.: On the van Kampen–Flores theorem. Math. Notes 59(5), 477–481 (1996)

  31. Živaljević, R.T., Vrećica, S.T.: The colored Tverberg’s problem and complexes of injective functions. J. Comb. Theory Ser. A 61(2), 309–318 (1992)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors thank the anonymous referee for many useful comments which improved the clarity and exposition of the manuscript, as well as for alerting the authors to connections with the square peg problem. The authors likewise thank Florian Frick and Pablo Soberón for helpful discussions and suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematics, Bard College, Annandale-On-Hudson, USA

    Leah Leiner & Steven Simon

Authors
  1. Leah Leiner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Steven Simon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Steven Simon.

Additional information

Editor in Charge: János Pach

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Leiner, L., Simon, S. Regular Polygonal Partitions of a Tverberg Type. Discrete Comput Geom 66, 1053–1071 (2021). https://doi.org/10.1007/s00454-021-00288-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-021-00288-2

Search

Navigation