Resolutions of Convex Geometries

  • Domenico Cantone
  • Jean-Paul Doignon
  • Alfio Giarlotta
  • Stephen Watson

Abstract

Convex geometries (Edelman and Jamison, 1985) are finite combinatorial structures dual to union-closed antimatroids or learning spaces.  We define an operation of resolution for convex geometries, which replaces each element of a base convex geometry by a fiber convex geometry.  Contrary to what happens for similar constructions–compounds of hypergraphs, as in Chein, Habib and Maurer (1981), and compositions of set systems, as in Möhring and Radermacher)–, resolutions of convex geometries always yield a convex geometry.  

We investigate resolutions of special convex geometries: ordinal and affine.  A resolution of ordinal convex geometries is again ordinal, but a resolution of affine convex geometries may fail to be affine.  A notion of primitivity, which generalize the corresponding notion for posets, arises from resolutions: a convex geometry is primitive if it is not a resolution of smaller ones.  We obtain a characterization of affine convex geometries that are primitive, and compute the number of primitive convex geometries on at most four elements.  Several open problems are listed. 

Published
2021-11-19
Article Number
P4.26