Frankl’s Conjecture for Large Families: Ilan Karpas’ Proof

Combinatorics and more 2018-03-12

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 $2^{n-1}$ subsets of $[n]$ . 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 $B$ is a union closed family of subsets of $[n]$ , and $|B| \ge 2^{n-1}$ then there exists an element $k \in [n]$ such that $|\{S \in B: k \in S\}| \ge |B|/2$ .

Theorem 2 (Karpas): If $A$ is a family of subsets of $[n]$ , $|A|\le 2^{n-1}$ with the property

(*) If $S\in A$ and $a,b \in S$ , $a\ne b$ then either $S \backslash \{a\}\in A$ or $S \backslash \{b\}\in A$ .

Then there exists an element $k \in [n]$ such that $|\{S \in A: k \in S\}| \le |A|/2$ .

The implication from Theorem 2 to Theorem 1 is very easy. If $B$ is a union-closed family and $A$ is the complement of $B$ , then $B$ satisfies (*). (Otherwise, $S \backslash \{a\}\in B$ and $S \backslash \{b\}\in B$ and their union $S$ must be in $B$ . If $B$ has at least $2^{n-1}$ elements then $A$ has at most $2^{n-1}$ elements. If $|\{S \in A: k \in S\}| \le |A|/2$ , then $|\{S \in B: k \in S\}| \ge |B|/2$ . We note that Condition (*) is weaker than the assertion that $A$ is union closed and indeed Theorem 2 is sharp.

Background (a little more than needed)

Edge boundary/influence terminology

For a family $A$ of subsets of $[n]$ its edge-boundary is defined by $E(A,\bar A)= \{(S,T) d(S,T)=1, S \in A, T \notin A\}$

The total influence of $A$ is defined by $I(A) = \frac {1}{2^{n-1}}|E(A,\bar A)|$

Up and down edge boundaries:

$E^-(A,\bar A)= \{(S,T) : d(S,T)=1, S \in A, T \notin A, T \subset S \}$

$E^+(A,\bar A)= \{(S,T) : d(S,T)=1, S \in A, T \notin A, S \subset T \}$

$I^+(A) =2^{-(n-1)}|E^+(A,\bar A)|$

$I^-(A) =2^{-(n-1})|E^-(A,\bar A)|$

Directional boundaries and individual influences

We now define:

$I_k^-(A)= 2^{-(n-1)}|\{S \in A, k \in S, S \backslash\{k\} \notin A \}|$ ,

$I_k^+(A)=2^{-(n-1)}|\{S \in A, k \notin S, S \cup \{k\} \notin A \}|$ ,

The influence of $k$ on A is defined by:

$I_k(A)=I_k^+(A)+I_k^-(A)$

Note that the assertion for Frankl’s conjecture is equivalent to: For every union-closed family $B$ there is $k$ such that $I_k^-(B) \ge I_k^+(B)$ . Equivalently for every family $A$ whose complement is union-closed (such families are called “simply rooted”) there is $k$ such that $I_k^+(A) \le I_k^-(A)$ .

Sensitivity/Pivotality

Now, fix a family $A$ of subsets of $[n]$ , for $S \in A$ , $h_k(S) = 1$ , if $S \delta \{k\}\not in A$ and $h_k(S) = 0$ otherwise. $h^+_k(S)=1$ if $k \in S$ and $h_k(S) = 1$ . (In other words, $k \in S$ and $S \backslash \{k\}\notin A$ .) $h^-_k(S)=1$ if $k \notin S$ and $h_k(S) = 1$ . (In other words, $k \notin S$ , and $S \cup \{k\}\notin A$ .) Define also $h(S) = h_1(S)+h_2(S)+\cdots h_n(S),$ $h^+(S) = h^+_1(S)+h^+_2(S)+\cdots + h^+_n(S),$ $h^-(S) = h^-_1(S)+h^-_2(S)+\cdots + h^-_n(S).$

Note that $I_k^+(A)=2^{-(n-1)}\sum_{S \in A} h_k^+(S)$ , and similarly for other types of influences.

Fourier

Let $f:\{0,1\}^n \to \{-1,1\}$ be a Boolean function defined as follows: $f(x)=-1$ if $x$ represents a set in $A$ , and $f(x)=1$ , otherwise.

We write $\hat A(S)=\hat f(S)$ .

It is well known and easy to see that $\hat A(\{k\})=I^+_k(A)-I^-_k(A)$ .

Parseval’s formula gives $\sum \hat A^2(S)=1$ . It follows easily from Parseval’s formula that $I_k(A)=\sum \{\hat A^2(S):k \in S\},$ and hence $I(A)=\sum \hat A^2(S)|S|.$

The proof:

We write $|A|=(1/2-\delta) 2^n$ .

Our assumption (*) on $A$ is that if $S\in A$ and $a,b \in S$ , $a\ne b$ then either $S \backslash \{a\}\in A$ or $S \backslash \{b\}\in A$ . In other words $h^+(S) \le 1$ for every $S \in A$ . This implies that