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

Combinatorics and more 2022-11-17

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.

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… . He also presents an appealing information-theoretic strengthening of the conjecture which may consist of a path toward a proof.

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 $2^{[n]}$ . Then there exists an antichain ${\cal G} \subset {\cal F}$ such that

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