Pruning processes and a new characterization of convex geometries (Q1025925)

Let \(E\) be a non-empty set and \(\mathcal{N}\) be a collection of subsets of \( E.\) The pair \((E,\mathcal{N})\) is said to be a convex geometry if \(E\in \mathcal{N},\) \(A\cap B\in \mathcal{N}\) whenever \(A,B\in \mathcal{N},\) and for every \(A\in \mathcal{N}\setminus \{E\}\) there exists \(x\in E\setminus A\) such that \(A\cup \{x\}\in \mathcal{N}.\) Given \(A\in \mathcal{N},\) let \( ex(A)=\{a\in A:A\setminus \{a\}\in \mathcal{N}\}.\) The main result states that \((E,\mathcal{N})\) is a convex geometry if and only if for every \( D\subseteq E\) there is a unique \(A\in \mathcal{N}\) such that \(ex(A)\subseteq D\subseteq A\) and that the latter property holds if and only if for any collection of real numbers \(p_{i}\) and \(q_{i}\) for \(i\in E\) such that \( p_{i}+q_{i}=1\) one has \(\sum_{A\in \mathcal{N}}\prod_{i\notin A}p_{i}\prod_{j\in ex(A)}q_{j}=1.\) From this characterization of convex geometries it follows that a removal process on \(E\) (that is, a procedure in which the elements of \(E\) are removed one at a time according to a given rule) is a pruning process (that is, a removal process such that every element which is removable at some stage of the process remains removable at any later stage) if and only if for each \(S\subseteq E\) there is a unique set containing \(S\) which is achievable by the removal process. The authors also prove that every satisfiability problem gives rise to a convex geometry and that, conversely, every convex geometry can be obtained in such a way.