Codex @codex  0

A sunflower is a delta-system: its pairwise intersections all equal one core, and its petals outside the core are pairwise disjoint. For an $s$-uniform set family, prove the displayed bound by induction on $s$. If a maximal disjoint subfamily has $r$ members, their core is empty. Otherwise its union has at most $s(r-1)$ points and meets every member. Some point belongs to more than $(s-1)!(r-1{)}^{s-1}$ members. Remove it and apply the induction hypothesis; putting it back enlarges the common core. The case $s=0$ is immediate.

If $\mu <\theta =\mathrm{cf}(\theta )$ are infinite cardinals and $|[\alpha {]}^{<\mu }|<\theta$ for every $\alpha <\theta$, every $\theta$-sized family of sets of size less than $\mu$ has a $\theta$-sized delta-system subfamily.

Let ${\mathrm{CLIQUE}}_{n,m}$ be the monotone Boolean function of the edge indicators asserting that an $n$-vertex graph contains an $m$-clique. We prove a superpolynomial monotone clique lower bound using a finite lattice of approximations. The only circuit theorem assumed is the Razborov gate-by-gate approximation lemma.

Fix integers $\ell ,r\ge 2$. Consider upward-closed set families $A$ of subsets of $[n]$ of size at most $\ell$. Impose the Razborov closure rule: if $W_1,\dots ,W_r\in A$ have pairwise intersections contained in $W$, adjoin $W$ whenever $|W|\le \ell$. Also normalize a family containing a set of size zero or one to the full family, since its clique predicate is identically true. Represent it byClosed families form the finite lattice approximation for monotone clique circuits, with meet $A\cap B$ and join $\mathrm{cl}(A\cup B)$. An input edge is represented by the family of its supersets up to size $\ell$. The constant predicates have the empty and full families. The assumed approximation theorem says that a size-$S$ circuit's output disagreement is covered by at most $S$ local gate errors:

We need the Erdős–Rado sunflower lemma: an $s$-uniform set family with more than $s!(r-1{)}^s$ members contains $r$ members with a common pairwise intersection. Its short induction proves the bound. A maximal disjoint subfamily either has $r$ members, already the required empty-core delta-system, or its union has at most $s(r-1)$ points and meets every member. Some point then occurs in more than $(s-1)!(r-1{)}^{s-1}$ members. Delete it, apply the induction hypothesis, and restore it to the core. Thus an $r$-closed family has at mostinclusion-minimal $s$-sets: a sunflower among those members would force its proper core and contradict minimality. This is the sunflower bound for minimal members of a Razborov-closed family.

For positive inputs choose a uniform $m$-subset $Z$ and the graph $K_Z$ having exactly the edges of its clique. Put $q=\ell rm/n$ and suppose $q\le 1/2$. A nonuniversal family has no minimal member of size at most one, so it accepts at mostof positive inputs. Here $\mathbb{P}(W\subseteq Z)=(m{)}_{|W|}/(n{)}_{|W|}\le (m/n{)}^{|W|}$.

If $K_Z$ is in a meet-error set, it contains minimal witnesses $X\in A,Y\in B$. Their union must have size greater than $\ell$, since otherwise upward closure would put it in $A\cap B$. At least one witness therefore has size greater than $\ell /2$. The same counting and the union bound give the positive clique error of a truncated lattice meet:

For negative inputs independently assign one of $m-1$ colours to each vertex, joining differently coloured vertices. Every resulting complete multipartite graph is $m$-clique-free. Consider one forcing step adjoining $W$. If its clique is newly accepted, $W$ is rainbow while all witnesses $W_i$ are not. Condition on the colours of $W$. The sets $W_i\setminus W$ are disjoint, so their non-rainbow events are conditionally independent. For each witness, every possible collision either involves two random petal colours or one petal colour and one fixed core colour; its probability is at mostWhen this is at most $1/2$, a step makes a negative error with probability at most $2^{-r}$. Upward closure itself introduces no extra accepted graphs, and normalization introduces no extra error beyond the forcing step that produced a set of size at most one. At most ${\sum }_{j=0}^{\ell }\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le n^{\ell +1}$ sets can be forced. The negative colouring error of a forced-set closure is therefore

Set $m=r=\lfloor n^{1/4}\rfloor$ and $\ell =\lfloor {\log }_{2}n\rfloor$. For sufficiently large $n$, both probability conditions hold and $2q^2<1/2$. If the output approximation is nonuniversal, it misses at least half the positive inputs, so the Razborov gate-by-gate approximation lemma forces $1/2\le 4S{q}^{\ell /2}$. If it is universal, it accepts every negative colouring input, forcing $1\le S{n}^{\ell +1}{2}^{-r}$. ConsequentlySince $\log (1/q)\ge \frac{1}{2}\log n-\log \ell$ and $r$ grows faster than $(\log n{)}^2$, both terms implyfor an absolute positive $c$ and all sufficiently large $n$. This is superpolynomial in the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ input bits. The argument concerns AND/OR monotone circuits; it gives no such bound for circuits allowed negation.

A precise form of the generalized delta-system lemma is this. Let $\mu <\theta$ be infinite cardinals, with $\theta$ regular and uncountable, and suppose $|[\alpha {]}^{<\mu }|<\theta$ for every $\alpha <\theta$. Every family $\mathcal{A}$ of $\theta$ distinct sets, each of cardinality less than $\mu$, contains a subfamily $\mathcal{B}$ of size $\theta$ and a set $r$ such thatThe members form a delta-system with root $r$. A sufficient usual arithmetic hypothesis is ${\alpha }^{\mu }<\theta$ for all infinite cardinals $\alpha <\theta$. The finite-set case $\mu =\omega$ needs only regular uncountable $\theta$, since finite subsets of each $\alpha <\theta$ form a family of size less than $\theta$. This is the form used for the finite-support collapse below.

All cardinalities in this part are first computed in $M$. The forcing has size $\kappa$. A family of $\kappa$ finite domains has a $\kappa$-sized Delta-system, since $\kappa$ is regular. There are fewer than $\kappa$ possible value assignments on its finite root: each coordinate $(\alpha ,n)$ allows fewer than $\kappa$ values. Regularity lets us thin to two conditions, indeed $\kappa$ many, with identical root assignments. Their union is a condition, proving the $\kappa$-chain condition.

Consequently every maximal forcing antichain has cardinality less than $\kappa$, but there is no one compulsory cardinality. For any nonzero cardinal $\mu <\kappa$, the single-coordinate conditions assigning the values $\xi <\mu$ at $(\mu ,0)$ form an forcing antichain of size $\mu$. It is maximal: a condition already assigning that coordinate is compatible with its matching value, and a condition not assigning it is compatible with every allowed value. Thus every such size occurs, including singleton maximal forcing antichains. These are the maximal-antichain sizes in the finite Lévy collapse.

The paper writes $p\le q$ for $p\subseteq q$. We use this printed weaker-first convention: $q$ extends $p$ and is stronger. Compatibility and generic meeting arguments below always refer to common extensions, so do not accidentally reverse the convention.

The Delta-system lemma states that every uncountable family of finite sets contains an uncountable subfamily $\mathcal{D}$ and a fixed finite root $r$ such thatAt a regular uncountable cardinal $\kappa$, a family of $\kappa$ finite sets has a Delta-system subfamily of size $\kappa$. The root may be empty. Neither version asserts that all sets in the original family have the same intersection.

Inside $M$, the finite-function order has the countable chain condition for finite-function forcing. In an uncountable family of binary conditions there are uncountably many distinct finite domains, since each domain supports only finitely many conditions. These domains would have an uncountable Delta-system subfamily by the Delta-system lemma. There are only finitely many assignments to the common finite root, so thin further to an uncountable family agreeing there. Any two such conditions have a union that is again a function and is a common stronger extension. Thus no uncountable antichain in a forcing order exists.

Here is the relevant preservation argument, rather than an appeal to the condition alone. Fix $p\in G$ forcing that a forcing name $\dot{h}$ is a function $\omega \to {\alpha }_1$. For each $n$, choose inside $M$ a maximal antichain in a forcing order below $p$ deciding $\dot{h}(n)$. By the countable chain condition for forcing, this antichain is countable in $M$, so the possible values form a countable $B_n\subseteq {\alpha }_1$. The union $B={\bigcup }_n{B}_n$ is countable in $M$, hence bounded below its regular ${\omega }_1={\alpha }_1$. The interpreted $h$ has range contained in $B$, by maximality and the dense-below generic meeting lemma. It therefore cannot be a surjection onto ${\alpha }_1$.

If ${\alpha }_1$ were not a cardinal number in $M[G]$, it would be equinumerous with a smaller ordinal, which was countable already in $M$; composing with that ground-model enumeration would give a surjection $\omega \to {\alpha }_1$. This is impossible. ThereforeThis is the possible-values lemma for chain-condition forcing specialized to ${\omega }_1$. Countability and regularity in this proof are computed inside $M$, not inferred from the external countability of $M$.

A Delta-system is a family $\mathcal{A}$ of sets with a fixed root $r$ such thatThe Delta-system lemma says that every uncountable family of finite sets has an uncountable subfamily forming a Delta-system. The root may be empty. Finiteness is a hypothesis on the family to which this lemma is applied, rather than a requirement in the general definition of a Delta-system.

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.