A minimal cutset of the Boolean lattice with almost all members (Q1262863): Difference between revisions

The authors consider cutsets in the lattice of subsets of a finite set, where cutting means intersecting all maximal chains. They show that there exist minimal cutsets containing a fraction arbitrarily close to 1 of all subsets. They start with the cutset associated with a partition of the total set into subsets \(S_ i\) consisting of all subsets which either contain a nonempty proper subset of every \(S_ i\) or contain all of some \(S_ i\), none of some \(S_ j\). Then by a probabilistic argument they show a small subset can be removed to make it minimal.