Ilan Karpas: Frankl’s Conjecture for Large Families

Posted on December 26, 2017 by Gil Kalai

Frankl’s conjecture

Frankl’s conjecture is the following: Let \cal A be a finite family of finite subsets of N=\{1,2,\dots,n\} which is closed under union, namely,  if S,T \in {\cal A} then also S \cup T \in {\cal A}.

Then there exists an element x which belongs to at least half the sets in \cal A.

Polymath 11 was devoted to this question (Wiki, first post, last post). We mentioned the conjecture in the first blog post over here and several other times, it was also mentioned over Lipton and Regan’s blog (here  and here) and various other places.

In this post  I want to mention a recent improvement by Ilan Karpas on the problem for large families.  Ilan showed that the conjecture is true when the family contains at least 2^{n-1} sets.

Notation: For a family \cal A and an element x \in N let {\cal A}_x=\{S \in {\cal A}: x \in S\}. The  abundance  a(x) of  an element x is |{\cal A}_x|/|{\cal A}|. Let’s call an element good,  if a(x) \ge 1/2. Frankl’s conjecture thus asserts that for every union closed family there is a good element.

The earlier record

Balla, Bòllobas and Eccles proved that for every union-closed family of subsets of N of size at least \frac{2}{3}2^n there is a good element. In fact, they showed that in this case the average of a(x) over all elements is at least 1/2. For the average statement this result is best possible. Eccles improved it further and showed that the assertion of Frankl’s conjecture holds when |{\cal A}|\ge (2/3-1/104)2^n.

The new results by Ilan Karpas.

Here are three main results from Karpas’ paper two results on union closed families

Theorem 1: The assertion of Frankl’s conjecture holds when |{\cal A}| \ge 2^{n-1}.

The proof is a surprisingly simple Fourier theoretic proof and it applies for a larger class of families: families with the property that every set not in \cal A  covers at most one set in \cal A.  (For this larger class the assertion of Frankl’s conjecture may fail when |{\cal A}|  < 2^{n-1})

Theorem 2: For some c>0, the assertion of Frankl’s conjecture holds when |{\cal A}|\ge (1-c) 2^{n-1}.

The proof is a more involved Fourier-based proof. It also uses the following result of independent interest.

Theorem 3: for any union-closed family, the number of sets which are not in \cal A  that cover a set in \cal A  is at most 2^{n-1}. (The inequality is tight.)

As far as I know this is the first time Fourier’s method helps for Frankl’s problem.  I wonder what is the potential of this method.

Abigail Raz’ result

In a recent very nice paper Abigail Raz’ showed that a nice extension of Frankl’s conjecture proposed in polymayh11 fails.

 

This entry was posted in Combinatorics, Open problems and tagged , , , . Bookmark the permalink.

4 Responses to Ilan Karpas: Frankl’s Conjecture for Large Families

  1. Ilan Karpas says:
    December 29, 2017 at 9:00 pm

    Thanks, Gil!

    Let me just mention another conjecture I have on the same lines of Theorem 3. I’ll state it only for families whose size is a power of two, but one can think of several ways to extend it for all sizes.

    \underline{Conjecture:} For any union-closed family \mathcal{A} of subsets of [n] of size |\mathcal{A}| = 2^k, k \leq n. Then the number of sets not in \mathcal{A} that cover a set of \mathcal{A} is at most (n-k)2^k.

    If true this would be tight, as one can see by taking \mathcal{A} = 2^{[k]}.

    Reply

  2. Pingback: Frankl’s Conjecture for Large Families: Ilan Karpas’ Proof | Combinatorics and more

  3. Pingback: Amazing: Justin Gilmer gave a constant lower bound for the union-closed sets conjecture | Combinatorics and more

Leave a comment