Razborov closure

Fix a finite ground set $V$, an integer $r\ge 2$ and a size limit $\ell$. The Razborov closure of a set family $\mathcal{F}\subseteq \{A\subseteq V:|A|\le \ell \}$ repeatedly adjoins a set $W$ of size at most $\ell$ whenever existing members $W_1,\dots ,W_r$ satisfyAll adjoined sets remain in the same truncated ambient family. The process terminates because that family is finite. The final family is the least family containing $\mathcal{F}$ that is closed under the rule, so the result does not depend on the order of additions.

For $r=2$, the members $\{1,2\}$ and $\{1,3\}$ force $\{1\}$. In the finite lattice approximation for monotone clique circuits, this rule supplies a closure operation used to form approximate joins. It can add a smaller witness, which is why closure constrains the number of inclusion-minimal members.^[ref]

An inclusion-minimal $s$-set in an upward-closed family cannot belong to an $r$-member delta-system of such minimal sets: its proper core would be adjoined by Razborov closure, violating minimality. The Erdős–Rado sunflower lemma therefore bounds the number $a_s$ of minimal $s$-sets. This weaker factorial bound is sufficient for the superpolynomial monotone clique lower bound.

For $r\ge 2$, an $r$-closed set family has at most $(r-1{)}^k$ inclusion-minimal members of size $k$. This is stronger than the factorial estimate obtained from the Erdős–Rado sunflower lemma alone.

Here is the induction on $r$. For $r=2$, two distinct minimal members force their proper intersection, a contradiction, so at most one minimal member exists. For $r>2$, choose a minimal $k$-set $Z$ and group the minimal members $X$ by $W=X\cap Z$. The remainder $X\setminus Z$ is minimal in the family of sets $B$ outside $Z$ for which $B\cup W$ belongs to the original family.

That remainder family is $(r-1)$-closed: adding $Z$ as the final witness turns each $(r-1)$-witness forcing step into an original $r$-witness step. Induction bounds the group for $W$ by $(r-2{)}^{k-|W|}$; the group $W=Z$ contains only $Z$. Therefore the binomial theorem givesThe case $k=0$ has at most the single empty set. The forcing argument explains why the stronger bound uses the full closure rule rather than only a sunflower prohibition.^[ref]