Frankl’s conjecture asserts that a for every finite family of of finite sets that is closed under union, there is an element that belongs to at least half the sets in the family. We mentioned the problem in our very first post, and Tim Gowers ran polymath 11 in attempt to solve it (first post, wikipage). See also this post over GLL and this post.

Here, I want to show Ilan Karpas’ proof (that we mentioned in this post) that the conjecture is correct for “large” families, namely, for families of at least subsets of . Karpas’ proof is taken from his paper Two results on union closed families.

Can Fourier methods solve Frankl’s conjecture? I hope we could have a small discussion about it and related matters, and, in any case, I myself have some comments that I will leave to the comment section.

## The theorem

**Theorem (Karpas):** If is a union closed family of subsets of , and then there exists an element such that .

**Theorem 2 (Karpas):** If is a family of subsets of , with the property

(*) If and , then either or .

Then there exists an element such that .

The implication from Theorem 2 to Theorem 1 is very easy. If is a union-closed family and is the complement of , then satisfies (*). (Otherwise, and and their union must be in . If has at least elements then has at most elements. If , then . We note that Condition (*) is weaker than the assertion that is union closed and indeed the assertion of Theorem 2 ~~is sharp~~ do not hold when is large. (See remark below.)

## Background (a little more than needed)

## Edge boundary/influence terminology

For a family of subsets of its edge-boundary is defined by

The total influence of is defined by

### Up and down edge boundaries:

## Directional boundaries and individual influences

We now define:

,

,

The influence of on A is defined by:

Note that the assertion for Frankl’s conjecture is equivalent to: For every union-closed family there is such that . Equivalently for every family whose complement is union-closed (such families are called “simply rooted”) there is such that .

## Sensitivity/Pivotality

Now, fix a family of subsets of , for , , if and otherwise. if and . (In other words, and .) if and . (In other words, , and .) Define also

Note that , and similarly for other types of influences.

## Fourier

Let be a Boolean function defined as follows: if represents a set in , and , otherwise.

We write .

It is well known and easy to see that .

Parseval’s formula gives . It follows easily from Parseval’s formula that and hence

## The proof:

We write .

Our assumption (*) on is that if and , then either or . In other words for every . This implies that

(1) .

We assume that Frankl’s conjecture is false namely that , for every , or equivalently that

(2) , .

Summing over all s it follows that hence

(3) .

From it follows that

(4) .

Note that

(5)

But

(6)

Combining (4,5,6) we get

, or

(7) .

(1) and (7) gives , a contradiction.

### Like this:

Like Loading...