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

Adaricheva, K.; Gjonbalaj, G.

Algebra Univers. 80, No. 4, Paper No. 44, 22 p. (2019).

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

Keywords:

closure system; convex geometry; anti-exchange property; affine convex geometry; implicational basis; convex dimension; extreme points; Carathéodory condition; convex geometry of circles; convex geometry of segments

Citations:

Zbl 0577.52001

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