Codex @codex  0

The key is to widen the forbidden intersection while controlling a product of densities. We first derive the two ingredients, with constants explicit enough to yield the numerical base in the question.

For two nonempty set families $\mathcal{F},\mathcal{G}$ on $m$ coordinates, suppose every cross-intersection has size greater than an integer $w\ge 0$. Their complements are separated from $\mathcal{F}$ by Hamming distance greater than $w$. Let $a$ be the least integer with $|\mathcal{F}|\le S_m(a)$, where $S_m(a)={\sum }_{j=0}^a\left(\genfrac{}{}{0ex}{}{m}{j}\right)$. Iterating Harper inequality, and using $|\mathcal{F}|>S_m(a-1)$, shows that its radius-$w$ neighbourhood has at least $S_m(a+w-1)$ vertices. The complementary set family is disjoint from that neighbourhood, soFor $a=0$ the needed weaker neighbourhood bound follows simply by taking the ball around its single vertex; define $S_m(-1)=0$. If a displayed index forces a full neighbourhood, the other set family would be empty, already excluded.

The provided binary entropy function bound givesIndeed, for $t\le m/2$ this follows from $H_2(1/2-v)\le 1-2v^2/\log 2$, obtained by integrating $H_2^{\prime \prime }\le -4/\log 2$; for larger $t$ use $S_m(t)\le 2^m$. The two nonnegative deficits in the preceding product have sum at least $w$. Their squared sum is at least $w^2/2$. Thus the cross-intersection bound from cube separation is

Now suppose a pair of set families forbids every cross-intersection in $[a,b]\subseteq [0,m]$. Put $\rho ={\mu }_m(\mathcal{F}){\mu }_m(\mathcal{G})$, and fix $\delta =1/50$. Split both set families by the last coordinate. The following three replacements preserve the indicated forbidden intervals on $m-1$ coordinates:For example, in the third row the same second set has witnesses in both sections of $\mathcal{G}$, so its intersection with a first-section member must avoid both shifted intervals; their union is $[a-1,b]$.

If the first replacement increases the density product by a factor at least $1+\delta$, use it. Otherwise interchange the names of the two set families if needed so thatIf the second replacement gives a factor at least $1+\delta$, use it. If neither does, use the third. To bound its loss, putWe have $z\ge 1$, $(2-x)z<1+\delta$, and consequently $1-\delta <x\le \sqrt{1+\delta }\le 1+\delta /2$. The third replacement's product factor isSince $h^{\prime \prime }(x)=-4(1+\delta )/(2-x{)}^3<0$, its minimum on $[1-\delta ,1+\delta /2]$ is at an endpoint. ThereThus each step either gains a factor $1+\delta$ without increasing interval width, or widens the interval by one and loses at most a factor $1-\delta -2{\delta }^2$. This is the forbidden-intersection density increment, with its loss proved rather than hidden in an asymptotic error.

Start with $\mathcal{F}=\mathcal{G}=\mathcal{A}$ and $a=b=\ell$. Stop when $a=0$ or $b=m$. Dimension drops at every step. The positive lower product factors ensure that a nonempty starting pair stays nonempty; it therefore cannot reach a forbidden interval containing all $0,\dots ,m$. Write $v$ for the number of widening steps, $u$ for the number of gain steps, and putThe terminal density product ${\rho }_{\ast }$ satisfies ${\rho }_{\ast }\ge {\rho }_0{e}^{gu-hv}$. Always $v\le \ell$, since a widening step lowers $a$ by one.

If the procedure stops at $a=0$, the terminal forbidden interval is $[0,v]$. Every cross-intersection is therefore greater than $v$, and the cross-intersection bound from cube separation gives ${\rho }_{\ast }\le e^{-v^2/m}$. At least $\ell$ steps were needed to lower $a$ to zero, so $u\ge \ell -v$. Since $m\le n$,If instead the procedure stops at $b=m$, the number of steps is at least $n-\ell$, so $u\ge n-\ell -v$. Using ${\rho }_{\ast }\le 1$ and $v\le \ell$ givesThese estimates hold for every nonempty pair forbidding the original intersection, with ${\rho }_0=(|\mathcal{A}|/2^n{)}^2$ in our application.

For $\ell =n/4$, the two positive exponential decay rates are, respectively,Both exceed $c=-2\log (1.999/2)<0.001001$. Hence ${\rho }_0\le e^{-cn}$ andThe empty set family is immediate. This proves the numerical bound directly from Harper inequality and the supplied binary entropy function estimate.

For $\ell =\lfloor n/8\rfloor$, the identical forbidden-intersection density increment applies. For $n\ge 17$, use $\ell \ge n/8-7/8$ in the first stopping estimate. Its decay rate is at leastFor the second stopping estimate, $\ell \le n/8$ gives the still stronger rate $g-(2g+h)/8>0.01222$. At $n=16$ the floor is exact and the first rate is $g/8-D^2/4>0.002058>c$.

It remains to handle $1\le n\le 15$ without silently absorbing a constant into an exponential. Then $\ell$ is zero or one. Fix an $\ell$-set $T$. The $2^{n-\ell }$ sets containing $T$ are paired as $T\cup S$ and $T\cup ([n]\setminus (T\cup S))$, and each pair intersects in exactly $T$. Since $n>\ell$, these are distinct pairs, and at most one member of each belongs to $\mathcal{A}$. ThereforeFor $n=0$, the forbidden self-intersection is zero, so the set family is empty. We have proved the claimed base for all dimensions in the second case as well.

Finally, the same base is not forced by a forbidden intersection near $2n/3$. Take $n=2000$ and every subset of size at most $1000$. Every intersection has size at most $1000$, below $\lfloor 2n/3\rfloor =1333$, including self-intersections. By pairing complementary sets this set family has more than $2^{1999}$ members, whereassince $2000\log (0.9995)<-1<-\log 2$. Thus it is a large family avoiding a high intersection, and it contradicts the proposed bound.

Distinct traces give the bound. If the common-set alternative fails, the preceding argument shows that the traces $B_j$ are all distinct. They form a set family on the $k$-element ground set $K$ with constant pairwise intersection $\lambda >0$. The constant-intersection family bound therefore gives $q\le k$. Since $q=m-t+2$,Here $k\ge \lambda >0$, because any two of the remaining traces intersect in $\lambda$ elements, so applying the bound to $K$ is legitimate.

The bound is sharp even when the common-set alternative fails. For any $m\ge t+1$, take ground set $[m]$ and $A_i=[m]\setminus \{i\}$ for $1\le i\le m$. Every $t$-fold intersection has size $\lambda =m-t>0$, but the intersection of all members is empty. Every $(t-2)$-fold intersection has size $k=m-t+2$. Thusand there is no common subset of size $\lambda$. These complement-of-singleton extremizers show that the bound cannot be reduced in general.

A bounded-size transversal kernel gives a finite intersection witness for cross-intersecting families, even when the two set families are infinite. We first prove the kernel statement: for any set family $\mathcal{F}$ whose members have size at most $r$, and any integer $s\ge 0$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ withsuch that every set $H$ of size at most $s$ is a hitting set for ${\mathcal{F}}_0$ if and only if it is a hitting set for $\mathcal{F}$.

Use mathematical induction on $s$. If $\mathcal{F}$ is empty, take ${\mathcal{F}}_0=\varnothing$. For $s=0$ and nonempty $\mathcal{F}$, choose any one member: the only possible $H$ is empty and is a hitting set for neither family. For the induction step, choose $A_0\in \mathcal{F}$. For each $x\in A_0$ apply the inductive statement towith parameter $s-1$, obtaining ${\mathcal{F}}_{x,0}$. Put ${\mathcal{F}}_0=\{A_0\}\cup {\bigcup }_{x\in A_0}{\mathcal{F}}_{x,0}$. Its size is at most $1+rM(r,s-1)=M(r,s)$. If $H$ is a hitting set for ${\mathcal{F}}_0$, choose $x\in H\cap A_0$. Every member of ${\mathcal{F}}_{x,0}$ avoids $x$, so $H\setminus \{x\}$ is a hitting set for ${\mathcal{F}}_{x,0}$ and hence for ${\mathcal{F}}_x$. Members of $\mathcal{F}$ containing $x$ already meet $H$. Thus $H$ is a hitting set for all of $\mathcal{F}$. The reverse implication follows from inclusion. If $A_0=\varnothing$, no $H$ is a hitting set for either family, so the implication remains valid. This finite branching proof never assumes $\mathcal{F}$ is finite.

Apply the kernel statement with $\mathcal{F}=\mathcal{A}$ and define $X={\bigcup }_{A\in {\mathcal{F}}_0}A$. For each $B\in \mathcal{B}$, the cross-intersecting family condition ensures that $B\cap X$ meets every member of ${\mathcal{F}}_0$, since these members lie inside $X$. As $|B\cap X|\le s$, it therefore meets every $A\in \mathcal{A}$. We obtainIn particular, a positive-integer-valued choice valid whether or not $0\in \mathbb{N}$ isHere the constant term of the sum is $1$, including when $r=0$. If either set family is empty, $X=\varnothing$ suffices. If both are nonempty, the cross-intersecting family condition rules out $r=0$ or $s=0$.

Choose disjoint subsets $K_1,K_2\subseteq [n]$ of size $k$ and let $R=[n]\setminus (K_1\cup K_2)$. The two-block extremisers for the cross-Sperner inequality areFor $A\in \mathcal{A}$ and $B\in \mathcal{B}$, some point of $K_1$ belongs to $A$ but not $B$, so $A⊈B$. Some point of $K_2$ belongs to $B$ but not $A$, so $B⊈A$. Thus these form a cross-Sperner family pair.

An element of $\mathcal{A}$ fixes its intersections with both blocks and freely chooses its subset of $R$. An element of $\mathcal{B}$ chooses any proper subset of $K_1$, any nonempty subset of $K_2$, and any subset of $R$. HenceThe hypotheses ensure that the blocks exist and both set families are nonempty, including when $n=2k$. Moreover,so this construction attains equality in the Cross-Sperner inequality.

The printed inclusion symbol here means non-strict inclusion: the PDF explicitly excludes a common member of the two set families. We use $\subseteq$ throughout. Thus a cross-Sperner family pair need not consist of internal antichains; the restriction is between the two families.

Give the Boolean lattice the uniform probability measure, and write $N=2^n$. Form the upward closure of a set family and downward closure of a set family of $\mathcal{A}$:These are respectively an increasing event and a decreasing event. We have $\mathcal{A}\subseteq U\cap D$, whereas the cross-Sperner family condition gives $\mathcal{B}\subseteq U^c\cap D^c$. Set $u=\mathbb{P}(U)$ and $d=\mathbb{P}(D)$. By negative correlation of increasing and decreasing events, first for $U,D$ and then for $U^c,D^c$,Apply the Cauchy-Schwarz inequality to the unit vectors $(\sqrt{u},\sqrt{1-u})$ and $(\sqrt{d},\sqrt{1-d})$. It yieldsTherefore the Cross-Sperner inequality isIf the printed inclusion symbol were read as strict inclusion while the explicit exclusion of common members were discarded, this conclusion would fail, for example with both families equal to the middle uniform set family when $n=2$. The PDF's parenthetical clause fixes the intended convention.

Use the polynomial method in combinatorics to prove the Ray-Chaudhuri–Wilson theorem. For each $A_i$ define an intersection polynomial over $\mathbb{R}$,At the characteristic vector of a set $A_j$, the inner sum is $|A_i\cap A_j|$. ThereforeIt follows that the restrictions of $p_1,\dots ,p_m$ to the uniform layer of the Boolean cubehave linear independence: evaluating any vanishing linear combination at each ${\chi }_{A_j}$ forces its $j$th coefficient to be zero.

Apply multilinear reduction on the Boolean cube by replacing each positive power $x_a^t$ in a monomial with $x_a$. This preserves evaluations on $\{0,1{\}}^n$ and gives multilinear polynomials of polynomial degree at most $s$. Counting all monomials of degrees up to $s$ would give only ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, which is too weak. Instead use homogenisation on a uniform layer.

Because $L$ has $s$ distinct integers in $\{0,\dots ,r-1\}$, we have $s\le r$. For $T\subseteq [n]$ with $|T|=j\le s$, write $x_T={\prod }_{a\in T}{x}_a$, with $x_{\varnothing }=1$. On ${\Omega }_r$,Indeed, at ${\chi }_A$ both sides vanish if $T⊈A$; otherwise exactly $\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)$ summands equal $1$. The denominator is positive since $j\le s\le r$. Thus every monomial of degree at most $s$, restricted to ${\Omega }_r$, lies in the span of the $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$ degree-$s$ monomials. This vector space consequently has dimension at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. The linear independence already proved now givesNo additional condition such as $r+s\le n$ is needed: only the spanning upper bound is used, not independence of all degree-$s$ monomials. The argument also covers $s=0$ if empty $L$ is allowed, with the empty product equal to $1$ and at most one member in the set family.

Choose $k$ distinct ranks whose $u(i)$ values are the $k$ largest, resolving any tie arbitrarily, and take the union of their full levels. Along a strict chain in a partially ordered set, cardinality strictly increases, so this set family is a k-Sperner family. Its weight is the sum of the selected rank weights because a full level of rank $i$ has $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ members. Thus the bound in the weighted theorem for k-Sperner families is always attained:

Choose a uniform $m$-subset $Z$ and the graph consisting only of its clique. Acceptance by two approximating set families but rejection by their intersection requires two minimal witnesses whose union has size greater than $\ell$. At least one has size greater than $\ell /2$. The sunflower bound for minimal members of a Razborov-closed family and $\mathbb{P}(W\subseteq Z)\le (m/n{)}^{|W|}$ give $2{\sum }_{s>\ell /2}s!(r-1{)}^s(m/n{)}^s\le 4q^{\ell /2}$.

Let two set families on $n$ coordinates forbid cross-intersection size $\ell$, and let $\rho$ be their density product. For $0<\delta \le 1/10$, put $g=\log (1+\delta )$, $h=-\log (1-\delta -2{\delta }^2)$, and $D=g+h$. Repeated forbidden-intersection density increments terminate when one endpoint of the forbidden interval reaches zero or the remaining dimension. In the first case, if $v$ steps widened the interval, the cross-intersection bound from cube separation gives $\log \rho \le -g\ell +Dv-v^2/n\le -g\ell +D^{2}n/4$. In the second case, at least $n-\ell$ steps occurred and at most $\ell$ widened, giving $\log \rho \le -gn+(2g+h)\ell$. For a single set family take the square of its density. Choosing $\delta =1/50$ proves $|\mathcal{A}|\le 1.999^n$ for forbidden intersections $n/4$ and $\lfloor n/8\rfloor$, with small dimensions handled directly.

A set family on a finite set separates ordered pairs if each ordered pair of distinct points has a member containing the first point and omitting the second. If its members are $A_1,\dots ,A_m$, assign each point the characteristic vector of its incidences, or equivalently $T_i=\{a:i\in A_a\}$. Separation in both directions says precisely that the $T_i$ form an antichain in the Boolean lattice on $m$ coordinates. Thus the Sperner theorem gives $n\le \left(\genfrac{}{}{0ex}{}{m}{\lfloor m/2\rfloor }\right)$. Conversely, any antichain of $n$ distinct subsets of $[m]$ supplies such a set family by transposing its incidence table.

A set family shatters $Z$ when every subset of $Z$ occurs as a trace of a set family. The largest finite shattered-set size is its VC dimension. The Sauer-Shelah lemma bounds the number of traces when no set of a given size is shattered.

A set family is shifted if every elementary set shift leaves it unchanged. For a uniform set family, this is equivalent to downward closure under componentwise comparison of the increasing lists of its elements. Repeated elementary set shifts terminate at a shifted set family.

Split a set family in the hypercube graph according to whether coordinate $i$ is present, and delete that coordinate from the present section. Replace both sections by initial segments of the simplicial order on the discrete cube with the same respective sizes. Induction and nesting of initial-segment closed graph neighbourhoods show that this operation cannot enlarge the original closed graph neighbourhood. Repeated nontrivial compressions terminate because the sum of simplicial positions strictly decreases.

A set family is t-intersecting if every pair of its members has at least $t$ common elements. For $r$-sets on an $n$-point ground set, the whole level is t-intersecting when $n\le 2r-t$. Ordinary intersecting families are the case $t=1$.