About an Erdős–Grünbaum Conjecture Concerning Piercing of Non-bounded Convex Sets | Discrete & Computational Geometry Skip to main content
Springer Nature Link
Log in

About an Erdős–Grünbaum Conjecture Concerning Piercing of Non-bounded Convex Sets

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

Abstract

In this paper, we study the number of compact sets needed in an infinite family of convex sets with a local intersection structure to imply a bound on its piercing number, answering a conjecture of Erdős and Grünbaum. Namely, if in an infinite family of convex sets in \(\mathbb {R}^d\) we know that out of every \(p\) there are \(q\) which are intersecting, we determine if having some compact sets implies a bound on the number of points needed to intersect the whole family. We also study variations of this problem.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Alon, N., Kleitman, D.J.: Piercing convex sets and the Hadwiger-Debrunner \((p, q)\)-problem. Adv. Math. 96(1), 103–112 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  2. Boltyanski, V., Soifer, A.: Geometric études in Combinatorial Mathematics. Center for Excellence in Mathematical Education, Colorado Springs (1991)

    MATH  Google Scholar 

  3. Diestel, R.: Graph Theory: Graduate Texts in Math., vol. 173. Springer (2005)

  4. Eckhoff, J.: A survey of the Hadwiger-Debrunner \((p, q)\)-problem. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry. The Goodman-Pollack Festschrift. Algorithms and Combinatorics, vol. 25, pp. 347–377. Springer, Heidelberg (2003)

  5. Erdős, P., Gallai, T.: On the minimal number of vertices representing the edges of a graph. Magyar Tud Akad. Mat. Kutató Int. Közl. 6, 181–203 (1961)

    Google Scholar 

  6. Hadwiger, H., Debrunner, H.: Combinatorial geometry in the plane, Holt, Rinehart and Winston, New York. vii+113pp, Translated by Victor Klee. With a new chapter and other additional material supplied by the translator (1964)

  7. Hadwiger, H., Debrunner, H.E.: Über eine Variante zum Hellyschen Satz. Arch. Math. 8(4), 309–313 (1957)

    Article  MATH  MathSciNet  Google Scholar 

  8. Helly, E.: Über Mengen konvexer Körper mit gemeinschaftlichen Punkte. Jahresber. Dtsch. Math.-Ver. 32, 175–176 (1923)

  9. Kleitman, D.J., Gyárfás, A., Tóth, G.: Convex sets in the plane with three of every four meeting. Combinatorica 21(2), 221–232 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  10. Kynčl, J., Tancer, M.: The maximum piercing number for some classes of convex sets with the \((4,3)\)-property. Electron. J. Comb. 15(R27), 1 (2008)

    Google Scholar 

  11. Montejano, L., Oliveros, D.: Tolerance in Helly-type theorems. Discrete Comput. Geom. 45(2), 348–357 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  12. Müller, T.: A counterexample to a conjecture of Grünbaum on piercing convex sets in the plane. Discrete Math. 313(24), 2868–2871 (2013)

  13. Soifer, A.: The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. Springer, New York (2009)

    Google Scholar 

  14. Tuza, Z.: Minimum number of elements representing a set system of given rank. J. Comb. Theory, Ser. A 52(1), 84–89 (1989)

  15. Tuza, Z.: Applications of the set-pair method in extremal hypergraph theory. In: Frankl, P. (ed.), Extremal Problems for Finite Sets, Conference, Visegrád (Budapest), Bolyai Soc. Math. Stud., vol. 3. János Bolai Math. Soc. 1994, 479–514 (1991)

Download references

Acknowledgments

The authors wish to acknowledge the support of CONACYT under project 166306 and support of PAPITT-UNAM under projects IN112614 and IA102013.

Author information

Authors and Affiliations

  1. UMDI-Juriquilla Facultad de Ciencias, Universidad Nacional Autónoma de México, Mexico City, Mexico

    Amanda Montejano

  2. Unidad-Juriquilla, Querétaro Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico City, Mexico

    Luis Montejano & Edgardo Roldán-Pensado

  3. Mathematics Department, University of Michigan, Ann Arbor, MI, 48109-1043, USA

    Pablo Soberón

Authors
  1. Amanda Montejano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luis Montejano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Edgardo Roldán-Pensado
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pablo Soberón
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pablo Soberón.

Additional information

Editor in Charge: János Pach.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Montejano, A., Montejano, L., Roldán-Pensado, E. et al. About an Erdős–Grünbaum Conjecture Concerning Piercing of Non-bounded Convex Sets. Discrete Comput Geom 53, 941–950 (2015). https://doi.org/10.1007/s00454-015-9664-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-015-9664-3

Keywords

Mathematics Subject Classification

Search

Navigation