Amazing: Justin Gilmer gave a constant lower bound for the union-closed sets conjecture

Posted on November 17, 2022 by Gil Kalai

Frankl’s conjecture (aka the union closed sets conjecture) asserts that if \cal F is a family of subsets of [n] (=: \{1,2,\dots,n \}) which is closed under union then there is an element k such that

|\{S \in {\cal F}: k \in S\}| \ge \frac {1}{2}|{\cal F}|.

Justin Gilmer just proved an amazing weaker form of the conjecture asserting that there always exists an element k such that

|\{S \in {\cal F}: k \in S\}| \ge  0.01 |{\cal F}|.

This is am amazing progress! Congratulations, Justin.

The breakthrough paper, just posted on the arXiv is:

A constant lower bound for the union-closed sets conjecture by Justin Gilmer

Abstract: We show that for any union-closed family  \mathcal{F} \subseteq 2^{[n]}, \mathcal{F} \neq \{\emptyset\} there exists an i \in [n]  which is contained in a 0.01 fraction of the sets in \mathcal F.

This is the first known constant lower bound, and improves upon the \Omega(\log_2(\mathcal{F}|)^{-1}) bounds of Knill and Wójick.

Our result follows from an information theoretic strengthening of the conjecture. Specifically, we show that if A,B are independent samples from a distribution over subsets of [n]  such that Pr[i \in A] < 0.01 for all i and H(A)>0, then H(A \cup B)> H(A).

______

Mike Saks who first told me about the breakthrough wrote “the bound comes from a simple clever idea (using information theory) and 5 pages of gentle technical calculations.” (I thank Mike, Ryan Alweiss, and Nati Linial who wrote me about it.)

We mentioned Frankl’s conjecture several times including here, here, here, and here. Polymath11 on Tim Gowers’s blog was devoted to the conjecture. Below the fold: What it will take to prove the conjecture in its full strength and another beautiful conjecture by Peter Frankl.

Update: A few days after Gilmers’ paper was posted there were some developments by four six groups of researchers.  Four papers by Ryan Alweiss, Brice Huang, and Mark Sellke;  Zachary Chase and Shachar Lovett;  Will Sawin; Luke Pebody,  settled a conjecture by Gilmer that allows pushing the bound to: \frac{3-\sqrt 5}{2}=0.381966… . In his paper, Will Sawin improved this lower bound by an additional small constant.  Chase and Lovett found in their paper a related variant of Frankl’s conjecture for which the bound is oprimal.  Will Sawin  and independently David Ellis found counter examples to Gilmer’s conjecture that would imply Frankl’s conjecture. 

What is the limit of Gilmer’s method and what it will take to prove the Frankl conjecture

Justin Gilmer’s mentions that proving a tight bout for Lemma 1 in the paper will push the 0.01 bound to \frac{3-\sqrt 5}{2}=0.381966… . (This was proved by now.) He also presents an appealing information-theoretic strengthening of the conjecture which may consist of a path toward a proof. (This was disproved by now.)

Another beautiful conjecture by Peter Frankl

To face a possible risk that Frankl’s “union closed” conjecture will be solved here is another beautiful conjecture by Peter Frankl.

A family of sets is convex if whenever A \subset B \subset C and A,C \in {\cal F} then also B \in {\cal F}.

Conjecture (P. Frankl):  Let {\cal F} be a convex family of subsets of [n]. Then there exists an antichain {\cal G} \subset {\cal F} such that

|{\cal G}|/|{\cal F}| \ge {{n} \choose {[n/2]}}/2^n.

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

22 Responses to Amazing: Justin Gilmer gave a constant lower bound for the union-closed sets conjecture

  1. Anonymous Mathematician says:
    November 18, 2022 at 7:50 am

    Anybody know what the function H is? I downloaded Gilmer’s paper, and was surprised to see he doesn’t define it!

    Reply
  2. Alec Edgington says:
    November 18, 2022 at 9:50 am

    Is H the Shannon entropy?

    Interesting result!

    Reply
  3. John says:
    November 20, 2022 at 3:05 am

    What’s the intuition behind H(p) = H(2p – p^2) being solved by an algebraic p? Is this example covered in any standard textbook? Looks like wolfram can’t solve it either.

    Reply
  4. Annonymous poster says:
    November 22, 2022 at 5:47 pm

    Looks like the bound was improved to some constant larger than 0.38 today.
    https://arxiv.org/abs/2211.11731

    Reply
  5. sniffnoy says:
    November 28, 2022 at 11:47 am

    So hopefully just as Gilmer’s paper set off a race to optimize it, hopefully Sawin’s paper will (or has) set off a race to figure out this δ and optimize that? 🙂

    Reply

  6. Pingback: Progress on the union-closed sets conjecture – SPP 2026

  7. Pingback: A Nice Example Related to the Frankl Conjecture | Combinatorics and more

  8. Pingback: The Gift of Nonconstructivity | Gödel's Lost Letter and P=NP

  9. Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more

  10. Pingback: Na wiskundige opwinding op sociale media is het probleem van de kleurige knikkers bijna opgelost

  11. Sam Hopkins says:
    February 8, 2023 at 4:08 pm

    Just posted to the arXiv today: “A proof of the union-closed sets conjecture” by Raffaele Scandone https://arxiv.org/abs/2302.03484. Apparently builds off of Glimer’s breakthrough with the innovation of considering a convex combination of $A$ and $A \cup B$ where $A$ and $B$ are independent samples from the uniform distribution over a union-closed family. Of course, we should wait until the details have been checked, but potentially very exciting news!

    Reply
    • ryeguy10 says:
      February 8, 2023 at 5:30 pm

      It’s wrong. The information contained in Z_{delta} magically disappears from his calculations.

      Reply
      • ryeguy10 says:
        February 8, 2023 at 5:53 pm

        Err he mishandles Z_{delta}, I think what he is basically doing is pretending there is new information at each step. This means he ends up greatly overestimating the amount of information in A^{delta}.

        Or, as Terry says, the first equality at the bottom of Page 4 is wrong.

  12. ryeguy10 says:
    February 8, 2023 at 5:33 pm

    His Proposition 1.2 is false, even with n=2. Let A be empty with probability a, let it be each of {1} and {2} with probability b-eps, and let it be {1,2} with probability a+2*eps. Then if a>b>eps>0, a+b=1/2, and eps is sufficiently small this is a counterexample. This counterexample due to Hans Yu.

    Reply

Leave a comment