Document Open Access Logo

Radon Numbers Grow Linearly

Author Dömötör Pálvölgyi

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.60.pdf
  • Filesize: 394 kB
  • 5 pages

Document Identifiers

Author Details

Dömötör Pálvölgyi
  • MTA-ELTE Lendület Combinatorial Geometry Research Group, Institute of Mathematics, Eötvös Loránd University (ELTE), Budapest, Hungary

Funding

  • Pálvölgyi, Dömötör: Research supported by the Lendület program of the Hungarian Academy of Sciences (MTA), under grant number LP2017-19/2017.

Acknowledgements

I would like to thank Boris Bukh and Narmada Varadarajan for discussions on [B. Bukh, 2010], Andreas Holmsen for calling my attention to the difference between restricted and multiset Radon numbers, especially for confirming that Theorem 2 also holds for multisets, and Gábor Damásdi, Balázs Keszegh, Padmini Mukkamala and Géza Tóth for feedback on earlier versions of this manuscript, especially for fixing the computations in the proof of Lemma 3. I would also like to thank my anonymous referees for several valuable suggestions.

Cite AsGet BibTex

Dömötör Pálvölgyi. Radon Numbers Grow Linearly. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 60:1-60:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.60

Abstract

Define the k-th Radon number r_k of a convexity space as the smallest number (if it exists) for which any set of r_k points can be partitioned into k parts whose convex hulls intersect. Combining the recent abstract fractional Helly theorem of Holmsen and Lee with earlier methods of Bukh, we prove that r_k grows linearly, i.e., r_k ≤ c(r₂)⋅ k.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Hypergraphs
  • Theory of computation → Computational geometry
Keywords
  • discrete geometry
  • convexity space
  • Radon number

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon, I. Bárány, Z. Füredi, and D. J. Kleitman. Point selections and weak ε-nets for convex hulls. Comb. Prob. Comput., 1:189-200, 1992. Google Scholar
  2. N. Alon, G. Kalai, J. Matoušek, and R. Meshulam. Transversal numbers for hypergraphs arising in geometry. Adv. in Appl. Math., 29:79-101, 2002. Google Scholar
  3. N. Alon and D. J. Kleitman. Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem. Adv. Math., 96:103-112, 1992. Google Scholar
  4. I. Bárány. A generalization of Carathéodory’s theorem. Disc. Math., 40:141-152, 1982. Google Scholar
  5. I. Bárány and P. Soberón. Tverberg’s theorem is 50 years old: a survey. Bull. Amer. Math. Soc. (N.S.), 55(4):459-492, 2018. Google Scholar
  6. B. Bukh. Radon partitions in convexity spaces. arXiv, 2010. URL: http://arxiv.org/abs/1009.2384.
  7. J. R. Calder. Some elementary properties of interval convexities. J. London Math. Soc., 2(3):422-428, 1971. Google Scholar
  8. J. A. de Loera, R. N. La Haye, D. Rolnick, and P. Soberón. Quantitative combinatorial geometry for continuous parameters. Discrete Comput. Geom., 57(2):318-334, 2017. Google Scholar
  9. J. A. de Loera, R. N. La Haye, D. Rolnick, and P. Soberón. Quantitative Tverberg theorems over lattices and other discrete sets. Discrete Comput. Geom., 58(2):435-448, 2017. Google Scholar
  10. J. A. de Loera, T. A. Hogan, F. Meunier, and N. H. Mustafa. Tverberg theorems over discrete sets of points. arXiv, 2018. URL: http://arxiv.org/abs/1803.01816.
  11. J. Eckhoff. Radon’s theorem revisited. In Contributions to geometry (Proc. Geom. Sympos., Siegen, 1978), pages 164-185, Basel, 1979. Birkhäuser. Google Scholar
  12. J. Eckhoff. The partition conjecture. Disc. Math., 221 (Selected papers in honor of Ludwig Danzer):61-78, 2000. Google Scholar
  13. R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner. The crossing Tverberg theorem. In Symposium on Computational Geometry (SoCG 2019), pages 38:1-38:13, 2019. Google Scholar
  14. A. F. Holmsen. Large cliques in hypergraphs with forbidden substructures. Combinatorica, 2019. accepted. URL: http://arxiv.org/abs/1903.00245.
  15. A. F. Holmsen and D.-G. Lee. Radon numbers and the fractional Helly theorem. Israel J. of Mathematics, 2019. accepted. URL: http://arxiv.org/abs/1903.01068.
  16. R. E. Jamison-Waldner. Partition numbers for trees and ordered sets. Pacific J. Math., 96(1):115-140, 1981. Google Scholar
  17. M. Katchalski and A. Liu. A problem of geometry in ℝⁿ. Proc. Amer. Math. Soc, 75:284-288, 1979. Google Scholar
  18. S. Letzter. Radon numbers for trees. Disc. Math., 340:333-344, 2017. Google Scholar
  19. F. W. Levi. On Helly’s theorem and the axioms of convexity. J. Indian Math. Soc., 15:65-76, 1951. Google Scholar
  20. S. Moran and A. Yehudayoff. On weak ε-nets and the Radon number. In Symposium on Computational Geometry (SoCG 2019), pages 51:1-51:14, 2019. Google Scholar
  21. Z. Paták. Properties of closure operators in the plane. arXiv, 2019. URL: http://arxiv.org/abs/1908.01677.
  22. P. Patáková. Bounding Radon’s number via Betti numbers. arXiv, 2019. URL: http://arxiv.org/abs/1909.08489.
  23. J. Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalte. Math. Ann., 83:113-115, 1921. Google Scholar
  24. P. Soberón. Tverberg partitions as weak ε-nets. Combinatorica, 39:447-458, 2019. Google Scholar
  25. H. Tverberg. A generalization of Radon’s theorem. J. London Math. Soc., 41:123-128, 1966. Google Scholar
  26. M. L. J. van de Vel. Theory of convex structures, volume 50. North-Holland Mathematical Library, Amsterdam, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact