Frankl’s conjecture (aka the union closed sets conjecture) asserts that if is a family of subsets of [n] (=: ) which is closed under union then there is an element such that

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

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 there exists an which is contained in a 0.01 fraction of the sets in .

This is the first known constant lower bound, and improves upon the bounds of Knill and Wójick.

Our result follows from an information theoretic strengthening of the conjecture. Specifically, we show that if are independent samples from a distribution over subsets of such that for all and , then .

______

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: =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 =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 and then also .

Conjecture (**P. Frankl**): Let be a convex family of subsets of . Then there exists an antichain such that

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

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

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

Is H the Shannon entropy?

Interesting result!

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.

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

Looks like the bound was improved to some constant larger than 0.38 today.

https://arxiv.org/abs/2211.11731

Also in https://arxiv.org/abs/2211.11504, https://arxiv.org/abs/2211.11689

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

This paper seems to optimize :

Click to access 2212.00658.pdf

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

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

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

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

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

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

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!

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

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.

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.

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