Dinur-Friedgut Theorem

For and there is some such that for any Intersecting Family of subsets of there exists of size at most and an Intersecting Family of subsets of such that

where is the Upward Closure of (in terms of ).

Proof

Let . Apply the Regularity Lemma for Boolean Functions with parameters where is to be chosen. That gives us some of size at most such that if is chosen -randomly from then

Define

by setting if is -Quasirandom Boolean Function and and otherwise Then

(because we have for to not be quasirandom and another if its sparse) This corresponds to the statement that

Note that is an Intersecting Family and
so we may assume that is monotone and hence each is monotone. It remains to prove that is Intersecting Family. Let such that . Then and are -Quasirandom Boolean Functions and . It follows that for appropriate we have

By averaging we can find such that and . Since is intersecting there must exist such that so is Intersecting Family.

Corollary

For every and there is some such that for every and every Intersecting Family where there is some with and an Intersecting Family of subsets of such that

Proof

Suppose not. Let . Then has density at least . Apply Dinur-Friedgut to to obtain and intersecting family of subsets of with . Note that since we find

for every Also if then using LYM Inequality:

for sufficiently large. But

But so this is a contradiction (as )