Helly Numbers of Polyominoes | Graphs and Combinatorics Skip to main content
Springer Nature Link
Log in

Helly Numbers of Polyominoes

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

We define the Helly number of a polyomino P as the smallest number h such that the h-Helly property holds for the family of symmetric and translated copies of P on the integer grid. We prove the following: (i) the only polyominoes with Helly number 2 are the rectangles, (ii) there does not exist any polyomino with Helly number 3, (iii) there exist polyominoes of Helly number k for any k ≠ 1, 3.

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

Similar content being viewed by others

References

  1. Bárány I., Matousek J.: A fractional Helly theorem for convex lattice sets. Adv. Math. 174(2), 227–235 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  2. Barbosa R.M., Coelho E.M.M., Dourado M.C., Szwarcfiter J.L.: The colorful helly theorem and general hypergraphs. Eur. J. Comb. 33(5), 743–749 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  3. Beck J.: Combinatorial games: Tic–Tac–Toe theory. Encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge (2008)

    Book  Google Scholar 

  4. Berge, C.: Graphs and hypergraphs. North-Holland, Amsterdam, New York ([rev. ed.] translated by edward minieka. edition) (1973)

  5. Cardinal J., Collette S., Ito H., Sakaidani H., Korman M., Langerman Taslakian P.: Cannibal animal games: a new variant of tic-tac-toe. In: Proceedings of the 27th European Workshop on Computational Geometry, pp. 131–134 (2011)

  6. Doignon J.P.: Convexity in crystallographic lattices. J. Geom. 3, 71–85 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dourado M.C., Protti F., Szwarcfiter J.L.: Computational aspects of the helly property: a survey. J. Brazil. Comput. Soc. 12(1), 7–33 (2006)

    MathSciNet  Google Scholar 

  8. Golomb S.W.: Polyominoes: Puzzles, Patterns, Problems, and Packings, 2nd edn. Princeton University Press, New Jersey (1996)

    Google Scholar 

  9. Golumbic M.C., Jamison R.E.: The edge intersection graphs of paths in a tree. J. Comb. Theory Ser. B 38(1), 8–22 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  10. Golumbic M.C., Lipshteyn M., Stern M.: Edge intersection graphs of single bend paths on a grid. Networks 54(3), 130–138 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Goodman, J.E., O’Rourke, J. (eds.): Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (2004)

  12. Graham, R.L., Grötschel, M., Lovász, L. (eds.): Handbook of combinatorics, vol. 1. MIT Press, Cambridge (1995)

  13. Hugh D., Hugh D.: Counting polyominoes: yet another attack. Discrete Math. 36(3), 191–203 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  14. Morishita, T.: Constructing a program for enumerating the helly number of polyominoes. Unpublished manuscript (in japanese) (2011). Available at: http://llati.upc.es/mkorman/papers/cpehnp.pdf.

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Université Libre de Bruxelles (ULB), Brussels, Belgium

    Jean Cardinal, Matias Korman & Stefan Langerman

  2. School of Informatics, Kyoto University, Kyoto, Japan

    Hiro Ito

Authors
  1. Jean Cardinal
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Hiro Ito
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Matias Korman
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Stefan Langerman
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Matias Korman.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cardinal, J., Ito, H., Korman, M. et al. Helly Numbers of Polyominoes. Graphs and Combinatorics 29, 1221–1234 (2013). https://doi.org/10.1007/s00373-012-1203-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-012-1203-x

Keywords