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

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 SellkeZachary 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.

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

1. Anonymous Mathematician says:

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

• sniffnoy says:

When applied to a random variable, it’s the Shannon entropy. When applied to a real number in [0,1], it’s the binary entropy function: https://en.wikipedia.org/wiki/Binary_entropy_function

• John says:

$H(X) = -\sum_c P(X = c) \log P(X = c)$ where c ranges over all possible values of the random variable X. Note that if P(X = c) = 0, it contributes 0 to the sum.

2. Alec Edgington says:

Is H the Shannon entropy?

Interesting result!

3. John says:

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.

• Will Sawin says:

@John

H(p)= H(q) if and only if q=p or q=1-p. So the equation is equivalent to 2p-p^2=1-p.

• Thanks! What a bummer. Spent a whole afternoon on it.

4. Annonymous poster says:

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

• anon says:
5. sniffnoy says:

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? 🙂