Quorum Constraints and Filters in Boolean Lattices

Abstract

We investigate constraints in finite Boolean lattices $⟨\mathcal{P}(X),\subseteq ⟩$ where $X$ is a finite set. The constraints studied here are of the form $⟨Z,k⟩$ where $Z\subseteq X$, $1\le k\le |Z|$. A set $I\subseteq X$ \emph{satisfies} $⟨Z,k⟩$ if $|I\cap Z|\ge k$. We characterize the sets satisfying collections of such constraints as filters (final segments) in $⟨\mathcal{P}(X)⟩$. We find yet other characterizations of filters including one by means of families of sets indexed by elements of $X$ so that the elements of the filter correspond to subfamilies with an empty intersection. Our characterizations are supported for algorithms. We also study the families of negated constraints and mixed families and find their characterizations. In the positive case, formulas built of constraints can be used to measure the complexity of filters (and thus also of antichains of their minimal elements). We find pathological filters with very simple descriptions when the disjunctions are allowed, but extremely complex descriptions when only conjunctions are allowed.