A tight lower bound for the hardness of clutters

Vahan Mkrtchyan, Hovhannes Sargsyan

A {\it clutter} (or {\it antichain} or {\it Sperner family}) $L$ is a pair $(V,E)$, where $V$ is a finite set and $E$ is a family of subsets of $V$ none of which is a subset of ano…