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

### 22 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.

• aquazorcarson says:

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

• anon says:

This paper seems to optimize $\delta$:

Click to access 2212.00658.pdf

GK: thanks!

• sniffnoy says:

Ah, yeah, looks like δ turns out to be pretty tiny… oh well!

6. Sam Hopkins says:

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!

• ryeguy10 says:

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

• ryeguy10 says:

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.

7. ryeguy10 says:

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.

• Sam Hopkins says:

Thanks for this information. And sorry for hyping a preprint without reading it carefully.