Proof (Katona). Let $A\subset {[n]}^{(r)}$ be an intersecting family. We need to prove that if $A\subset {[n]}^{(r)}$ is chosen uniformly, then

Let $x_1,x_2,\dots ,x_n$ be a random cyclic ordering of $\{1,2,\dots ,n\}$. An interval in this cyclic ordering is a set of the form $\{x_i,x_{i+1},\dots ,x_{i+r-1}\}$ for some $i$ (addition modulo $n$).

There are $n$ intervals, so we will be done if we can prove that at most $r$ of them belong to $A$. (That is because we can choose a random element of ${[n]}^{(r)}$ by first choosing a random cyclic ordering and then choosing a random interval in that ordering.)

For each $i$, let $I_{x_i}^{+}$ be the interval $\{x_{i+1},x_{i+2},\dots ,x_{i+r}\}$ and let $I_{x_i}^{-}$ be the interval $\{x_{i-r+1},\dots ,x_i\}$.

Without loss of generality $\{x_1,\dots ,x_r\}\in A$. Then any other interval in $A$ must be $I_{x_i}^{+}$ or $I_{x_i}^{-}$ for some $i\in \{1,\dots ,r-1\}$. We can’t have both. So at most $r-1$ more intervals.

In the equality case, we must have equality for every cyclic ordering. In the above argument, we cannot have $i$ with $I_{x_i}^{-}\in A$ and $I_{x_{i+1}}^{+}\in A$. Therefore, if we have $r$ sets, then there must exist $t$ such that the intervals are $I_{x_1}^{+},\dots ,I_{x_{t-1}}^{+},I_{x_t}^{-},\dots ,I_{x_{r-1}}^{-}$, together with $\{x_1,\dots ,x_r\}$. So there exists $t$ such that they all contain $x_t$.

Now let us show that $A=\{A\in {[n]}^{(r)}:x_t\in A\}$. Without loss of generality $t=r$ so our intervals are $\{x_i,\dots ,x_{i+r-1}\}$ for $i=1,2,\dots r$. Let $u=x_n$. Define a cyclic ordering that goes like this:

In this cyclic ordering, $\{u\}\cup I_u^{+}\setminus \{x_r\}=(p_1,p_2,p_3)=\{x_n,x_1,\dots ,x_{r-1}\}\notin A$ (sinc it is an interval in the other cyclic ordering). Next, note $I_u^{+}=(p_2,p_3,p_4)=\{x_1,\dots ,x_r\}\in A$. So by the property we have proved (that in any cyclic ordering we have $r$ consecutive intervals), $A=(p_3,p_4,p_5)\in A$ since $A$ is also an interval.

The proof is complete. □

Proof. Since ${(f_u)}_u=f_u$, we have $E_J^2=E_J$, so $E_J$ is a projection. Now we would like to show that

for every $f$, or equivalently that $⟨f,E_{J}f⟩=⟨E_{J}f,E_{J}f⟩$. Since $E_{J}f=E_J^{2}f$, it is enough to prove that $E_J$ is self-adjoint.

But

This proves that $E_J$ is self-adjoint, which is interesting property, but we in fact we didn’t need to write down the last line in the calculation above if all we want to deduce is that $⟨f,E_{J}f⟩=⟨E_{J}f,E_{J}f⟩$.

Now let $J\subset K$ and let $L=K\setminus J$. Write $x=(u,v,z)$ where $u\in {\{0,1\}}^J$, $v\in {\{0,1\}}^L$, $z\in {\{0,1\}}^{K^c}$. Then

Proof. For any $J\subset [n]$, define the mean-square density of $J$ to be $\parallel E_{J}f{\parallel }_2^2$.. Note that if $J\subset K$, then

Suppose now that $J$ does not satisfy the conclusion of the lemma. Let $u\in {\{0,1\}}^J$. Then for any $K\subset [n]\setminus J$, $\parallel E_J{f}_u{\parallel }_2^2\ge {(𝔼f_u)}^2$. If $f_u$ is not $\left(𝜀,\rho r\right)$-quasirandom, then there exists $K_u\subset [n]\setminus J$ and some $v\in {\{0,1\}}^{K_u}$ such that

Let $\zeta =\min \{p,1-p\}$. Also, $|K_u|\le r$. If we choose a random element of ${\{0,1\}}^{K_u}$, then it equals $v$ with probability $\ge {\zeta }^r$. Therefore,

But

so the LHS is $\mathrm{Var}(𝔼f_{u,w}-𝔼f_u)$ so it equals

So $\parallel {𝔼}_{K_u}{f}_u{\parallel }_2^2\ge {(𝔼f_u)}^2+{\zeta }^r{𝜀}^2$ in this case.

Let $K={\bigcup }_u{K}_u$. Then $pnorm\parallel E_K{f}_u{\parallel }_2^2\ge {(𝔼f_u)}^2+{\zeta }^r{𝜀}^2$ in this case.

Averaging over $u$, we deduce that

i.e. $\parallel E_{J\cup K}f{\parallel }_2^2\ge \parallel E_{J}f{\parallel }_2^2+\delta {\zeta }^r{𝜀}^2$.

We can now do an iteration. Start with $J_0=\varnothing$. At $i$-th stage, if $J_i$ doesn’t work, then replace it by $J_{i+1}=J_i\cup K_i$, using the argument just given, with $|K_i|\le r\cdot 2^{|J_i|}$. At each stage, mean square density goes up by at least $\delta {\zeta }^r{𝜀}^2$, so the process must terminate in a bounded number of steps. □

Proof. Suppose that $𝔼f^{(1∕2)}\le \frac{1}{2}$. By the Mean Value Theorem, there exists $s\in \left(p,\frac{1}{2}\right)$ such that

By the main corollary to the The Margulis–Russo formula (Corollary 6.10), it follows that $I(f^{(s)})\le \frac{1}{\zeta }$. By the $p$-biased Friedgut junta theorem, we can find a Boolean $J$-junta $h$ such that $\mathbb{P}[f^{(s)}\ne h^{(s)}]\le 𝜀$ and $|J|\le r(\zeta ,𝜀)$.

But $𝔼f^{(s)}\le 𝔼f^{(1∕2)}$ by monotonicity, so $\mathbb{P}[f^{(s)}=1]\le \frac{1}{2}$ $⟹$ $\mathbb{P}[h^{(s)}=1]\le \frac{1}{2}+𝜀\le \frac{3}{4}$ (as long as $𝜀\le \frac{1}{4}$) $⟹$ $\mathbb{P}[h^{(s)}=0]\ge \frac{1}{4}$. Therefore $\mathbb{P}[f^{(s)}=1|h^{(s)}=0]\le 4𝜀$. Therefore, there exists $u$ such that $h_u\equiv 0$ and $\mathbb{P}[f_u^{(s)}=1]\le 4𝜀$. By monotonicity, $\mathbb{P}[f_u^{(p)}=1]=𝔼f_u^{(p)}\le 4𝜀$, so choosing $𝜀<\frac{\alpha }{5}$, we have that

contradicting $\left(𝜀,\rho ,r\right)$-quasirandom, where $r=r(\zeta ,𝜀)$. □

Proof. It is convenient to reformulate the statement in terms of Boolean functions. So call $f:{\{0,1\}}^n\to \{0,1\}$ intersecting if for all $x,y$, $f(x)=f(y)=1⟹\exists i,x_i=y_i=1$.

Let $f:{\{0,1\}}^n\to \{0,1\}$ be a Boolean function and apply the regularity lemma with parameters $\left(\frac{𝜀}{10},p,r,\frac{𝜀}{2}\right)$, where $r$ is to be chosen. That gives us $J$ of size at most $T(𝜀,p,r)$ such that if $u$ is chosen ${\mu }_p$-randomly from ${\{0,1\}}^J$, then

Define $g:{\{0,1\}}^J\to \{0,1\}$ by setting $g(u)=1$ if $f_u^{(p)}$ is $\left(\frac{𝜀}{10},p,r\right)$-quasirandom, and $𝔼f_u^{(p)}\ge \frac{𝜀}{2}$ and $0$ otherwise. Then

(This corresponds to the statement that $|A\setminus \overline{B}|\le 𝜀$. $A=\{A:f({𝟙}_A)=1\}$, $B=\{B:g({𝟙}_B)=1\}$.)

Note that $\overline{A}$ is an intersecting family and $|\overline{A}\setminus \overline{B}|\ge |A\setminus B|$, so we may assume that $f$ is monotone, and hence that each $f_u$ is monotone. It remains to prove that $g$ is intersecting. Let $u,v\in {\{0,1\}}^J$ such that $g(u)=g(v)=1$. Then $f_u$ and $f_v$ are $\left(\frac{𝜀}{10},p,r\right)$-quasirandom and $𝔼f_u^{(p)},𝔼f_v^{(p)}\ge \frac{𝜀}{2}$. By Lemma 7.5 for appropriate $r$, it follows that $𝔼f_u^{(1∕2)},𝔼f_v^{(1∕2)}>\frac{1}{2}$.

By averaging, we can find $y,z\in {\{0,1\}}^{[n]\setminus J}$ such that $y_i=1⟺z_i=0$ and $f_u(y)=f_v(z))=1$. Since $f$ is intersecting, there must exist $j$ such that $u_i=v_j=1$, so $g$ is intersecting. □

Proof. Let $\alpha =\frac{|A|}{\left(\genfrac{}{}{0ex}{}{n}{r}\right)}$ and $\beta =\frac{|{\partial }_{s}A|}{\left(\genfrac{}{}{0ex}{}{n}{s}\right)}$. Define a bipartite graph by joining $A\in {[n]}^{(r)}$ to $B\in {[n]}^{(s)}$ if and only if $A\subset B$. Now pick a random edge. The probability that it joins $A$ to ${\partial }_{s}A$ is exactly $\alpha$. It is also at most $\beta$. So $\alpha =\mathbb{P}[\text{joins }A\text{ to }{\partial }_{s}A]\le \beta$. □

Proof. Pick a random pair $(A,B)$ with $A\in {[n]}^{(r)}$, $B\in {[n]}^{(s)}$, $A\subset B$. Then

Also, the probability is at most $\beta$. The result follows. □

Proof. Suppose not. Let $C=hacal\setminus \overline{B}$. Then $C$ has density $\ge 𝜀$. Apply the Dinur, Friedgut Theorem to $A$ to obtain $J$ and an intersecting family $B$ of subsets of $J$ with ${\mu }_p(\overline{A}\setminus \overline{B})\le \frac{𝜀}{4}$.

Note that since $C\cap \overline{B}=\varnothing$, ${\partial }_J^{s}C\cap \overline{B}=\varnothing$ for every $s>r$. Also, if $s\le r+n^{2∕3}$, then

for $n$ sufficiently large.

But (by law of total probability),

But $\overline{C}\subset \overline{A}\setminus \overline{B}$, so this is a contradiction. □