Skip to main content
SpringerLink
Log in

Description of closure operators in convex geometries of segments on the line

  • Published:
Algebra universalis Aims and scope Submit manuscript

Abstract

Convex geometry is a closure space \((G,\phi )\) with the anti-exchange property. A classical result of Edelman and Jamison (1985) claims that every finite convex geometry is a join of several linear sub-geometries, and the smallest number of such sub-geometries necessary for representation is called the convex dimension. In our work we find necessary and sufficient conditions on a closure operator \(\phi \) of convex geometry \((G,\phi )\) so that its convex dimension equals 2, equivalently, they are represented by segments on a line. These conditions, for a given convex geometry \((G,\phi )\), can be checked in polynomial time in two parameters: the size of the base set |G| and the size of the implicational basis of \((G,\phi )\).

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Adaricheva, K., Nation, J.B.: Bases of closure systems. In: Grätzer, G., Wehrung, F. (eds.) Lattice Theory: Special Topics and Applications. Springer, Basel (2016)

    MATH  Google Scholar 

  2. Dilworth, R.P.: Lattices with unique irreducible decompositions. Ann. Math. 2(41), 771–777 (1940)

    Article  MathSciNet  Google Scholar 

  3. Czédli, G.: Finite convex geometries of circles. Discrete Math. 330, 61–75 (2014)

    Article  MathSciNet  Google Scholar 

  4. Edelman, P.H., Jamison, R.: The theory of convex geometries. Geom. Dedic. 19, 247–274 (1985)

    Article  MathSciNet  Google Scholar 

  5. Eliaz, K., Richter, M., Rubinstein, A.: Choosing the two finalists. Econ. Theory 46, 211–219 (2011)

    Article  MathSciNet  Google Scholar 

  6. Kincses, J.: On the representation of finite convex geometries with convex sets. Acta Sci. Math. 82, 301–312 (2017)

    MathSciNet  MATH  Google Scholar 

  7. Koshevoy, G.: Choice functions and abstract convex geometries. Math. Soc. Sci. 38, 35–44 (1999)

    Article  MathSciNet  Google Scholar 

  8. Monjardet, B.: A use for frequently rediscovering a concept. Order 1, 415–417 (1985)

    Article  MathSciNet  Google Scholar 

  9. Richter, M., Rogers, L.G.: Embedding convex geometries and a bound on convex dimension. Discrete Math. 340, 1059–1063 (2017)

    Article  MathSciNet  Google Scholar 

  10. Wild, M.: The joy of implications, aka pure Horn functions: mainly a survey. Theor. Comput. Sci. 658, 264–292 (2017)

    Article  Google Scholar 

Download references

Acknowledgements

We are grateful to Hofstra University that provided funds for both authors to travel to the conference Algebras and Lattices in Hawai’i-2018, where the results of this paper were presented. We want to thank Madina Bolat (University of Illinois in Urbana-Champaign), for her valuable comments and the help in producing the pictures. Other comments were sent by Gabor Czédli, Michael Richter and Jean-Paul Doignon. Many improvements in the paper were done thanks to a careful review, and we would like to thank our reviewers.

Author information

Authors and Affiliations

  1. Department of Mathematics, Hofstra University, Hempstead, NY, 11549, USA

    K. Adaricheva

  2. Department of Mathematics, Tufts University, Medford, MA, 02155, USA

    G. Gjonbalaj

Authors
  1. K. Adaricheva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. Gjonbalaj
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to K. Adaricheva.

Additional information

Dedicated to Ralph Freese, Bill Lampe, and J.B. Nation.

Publisher's Note

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

This article is part of the topical collection “Algebras and Lattices in Hawaii” edited by W. DeMeo.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Adaricheva, K., Gjonbalaj, G. Description of closure operators in convex geometries of segments on the line. Algebra Univers. 80, 44 (2019). https://doi.org/10.1007/s00012-019-0620-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00012-019-0620-6

Keywords

Mathematics Subject Classification

Search

Navigation