×

Description of closure operators in convex geometries of segments on the line. (English) Zbl 1423.05003

Summary: Convex geometry is a closure space \((G,\phi)\) with the anti-exchange property. A classical result of P. H. Edelman and R. E. Jamison [Geom. Dedicata 19, 247–270 (1985; Zbl 0577.52001)] 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)\).

MSC:

05A05 Permutations, words, matrices
06A15 Galois correspondences, closure operators (in relation to ordered sets)
06B99 Lattices
52B55 Computational aspects related to convexity

Citations:

Zbl 0577.52001
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Adaricheva, K.; Nation, JB; Grätzer, G. (ed.); Wehrung, F. (ed.), Bases of closure systems, (2016), Basel · Zbl 1375.06005
[2] Dilworth, RP, Lattices with unique irreducible decompositions, Ann. Math., 2, 771-777, (1940) · Zbl 0025.10202
[3] Czédli, G., Finite convex geometries of circles, Discrete Math., 330, 61-75, (2014) · Zbl 1295.52004
[4] Edelman, PH; Jamison, R., The theory of convex geometries, Geom. Dedic., 19, 247-274, (1985) · Zbl 0577.52001
[5] Eliaz, K.; Richter, M.; Rubinstein, A., Choosing the two finalists, Econ. Theory, 46, 211-219, (2011) · Zbl 1205.91051
[6] Kincses, J., On the representation of finite convex geometries with convex sets, Acta Sci. Math., 82, 301-312, (2017) · Zbl 1399.52003
[7] Koshevoy, G., Choice functions and abstract convex geometries, Math. Soc. Sci., 38, 35-44, (1999) · Zbl 0943.91031
[8] Monjardet, B., A use for frequently rediscovering a concept, Order, 1, 415-417, (1985) · Zbl 0558.06010
[9] Richter, M.; Rogers, LG, Embedding convex geometries and a bound on convex dimension, Discrete Math., 340, 1059-1063, (2017) · Zbl 1372.52002
[10] Wild, M., The joy of implications, aka pure Horn functions: mainly a survey, Theor. Comput. Sci., 658, 264-292, (2017) · Zbl 1418.03144
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.