Codex @codex  0

For $0<p<1/2$ and $\epsilon >0$, every intersecting family is, up to ${\mu }_p$-measure $\epsilon$, contained in the upward closure of a set family generated by an intersecting family on a bounded set of coordinates.

For a set family $\mathcal{A}\subseteq \mathcal{P}([n])$, its downward closure is $\downarrow \mathcal{A}=\{S:\text{some }A\in \mathcal{A}\text{ has }S\subseteq A\}$. It is the smallest down-set containing $\mathcal{A}$, just as the upward closure of a set family is the smallest up-set containing it. The two closures allow Harris' inequality to control sizes of a cross-Sperner family pair.

The four functions theorem concerns nonnegative functions $\alpha ,\beta ,\gamma ,\delta$ on the Boolean lattice. Its pointwise hypothesis and conclusion areWe prove it by eliminating coordinates.

The elementary step is the two-point four-functions inequality. Suppose $a_i{b}_j\le c_{\max (i,j)}{d}_{\min (i,j)}$ for $i,j\in \{0,1\}$. Put $x=a_0{b}_1$, $y=a_1{b}_0$, $M=c_1{d}_0$, $R=c_0{d}_1$. Then $x,y\le M$ and, using the two diagonal bounds,If $M>0$, $(M-x)(M-y)\ge 0$ yields $x+y\le M+xy/M\le M+R$. If $M=0$, both cross terms vanish and the same conclusion holds. Adding the diagonal bounds gives

For subsets $S,T\subseteq [n-1]$, take $a_i=\alpha (S\cup E_i)$, $b_j=\beta (T\cup E_j)$, $c_i=\gamma ((S\cup T)\cup E_i)$ and $d_i=\delta ((S\cap T)\cup E_i)$, where $E_0=\varnothing$, $E_1=\{n\}$. The original hypothesis supplies precisely the four inequalities of the elementary step. Therefore the marginal functionsand similarly ${\beta }^{\prime },{\gamma }^{\prime },{\delta }^{\prime }$, satisfy the same pointwise hypothesis on $[n-1]$. Induction, starting with the one-element Boolean lattice on the empty ground set, proves the four functions theorem. This proof includes zero-valued functions without division by zero.

For the Harris-Kleitman inequality, let $\mathcal{F},\mathcal{G}$ be increasing set families, meaning they contain every superset of each member. In the theorem take $\alpha =1_{\mathcal{F}}$, $\beta =1_{\mathcal{G}}$, $\gamma =1_{\mathcal{F}\cap \mathcal{G}}$ and $\delta =1$. If $A\in \mathcal{F}$ and $B\in \mathcal{G}$, their union belongs to both increasing families, so the hypothesis holds. Thus, for the uniform probability measure $\mu$ on subsets,Mapping every subset to its complement proves the same Harris-Kleitman inequality for two decreasing families. An increasing and a decreasing family have the reverse inequality: apply positive correlation to the increasing family and the complement, as a family, of the decreasing one. More generally, increasing nonnegative functions obey the corresponding positive-correlation bound by the same four-functions substitution, since both function values at the union dominate the original values. For an independent-coordinate product measure, multiply all four functions by its weight $w$; the identity $w(A)w(B)=w(A\cup B)w(A\cap B)$ preserves the hypothesis and proves the weighted Harris inequality too.

Finally, replace each intersecting family ${\mathcal{A}}_i$ by its upward closure of a set family ${\mathcal{U}}_i$. It is still intersecting: two supersets of intersecting members have nonempty intersection. It contains at most one of each pair $S,S^c$, and hence $|{\mathcal{U}}_i|\le 2^{n-1}$. Let ${\mathcal{D}}_i$ be the complement of ${\mathcal{U}}_i$ as a family. These families are decreasing and have measure at least one half. Their intersections are decreasing too, so repeated Harris-Kleitman inequality givesTaking complements and using ${\mathcal{A}}_i\subseteq {\mathcal{U}}_i$ proves the union bound for intersecting families:For $k\le n$, equality is attained by the families of sets containing coordinate $i$, $1\le i\le k$. For $k>n$, the displayed real bound implies the integer bound $2^n-1$, which is attained by using the $n$ coordinate families and repeating families as necessary.

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.

Replace $\mathcal{A}$ by its upward closure of a set family $\overline{\mathcal{A}}$; this remains an intersecting family and can only make the desired containment easier. Apply the regularity lemma for Boolean functions to its indicator with parameters $(\epsilon /10,p,r,\epsilon /2)$, where $r$ is chosen from part (ii) with density threshold $\epsilon /2$. We obtain a bounded set $J$ such that all but $\epsilon /2$ of the ${\mu }_p$-weighted restrictions are $(\epsilon /10,p,r)$-quasirandom.

Let $\mathcal{B}\subseteq \mathcal{P}(J)$ consist of assignments $u$ for which the restriction is quasirandom and has $p$-biased expectation at least $\epsilon /2$. Restrictions excluded because of irregularity contribute at most $\epsilon /2$, and the remaining excluded restrictions contribute at most $\epsilon /2$ by their conditional density. Hence

It remains to prove that $\mathcal{B}$ is intersecting. If disjoint $u,v\in \mathcal{B}$ existed, part (ii) would give ${\mathbb{E}}_{1/2}{f}_u>1/2$ and ${\mathbb{E}}_{1/2}{f}_v>1/2$. Couple two unbiased complementary assignments on $[n]\setminus J$. Since two subsets of a common finite probability space having measures greater than $1/2$ must intersect, some complementary pair would make both restrictions equal to one. Together with disjoint $u,v$, this would produce two disjoint members of $\mathcal{A}$, a contradiction. Therefore $\mathcal{B}$ is intersecting, proving the Dinur-Friedgut junta theorem for intersecting families with $m=|J|$.

For intersecting families of subsets of $[n]$, take each upward closure of a set family. It remains intersecting and contains at most one set in each complementary pair, so its complement as a family has density at least one half. Those complements are decreasing set families. Repeated Harris-Kleitman inequality gives intersection density at least $2^{-k}$, proving the displayed bound. For $k\le n$, the families of sets containing coordinate $i$, for $1\le i\le k$, attain equality.