Update: Peter Frankl brought to my attention that the very same example appeared in a paper by Dynkin and Frankl “Extremal sets of subsets satisfying conditions induced by a graph“.
As a follow up to my previous post about Gilmer’s breakthrough regarding Frankl’s conjecture, here is a very nice example (from the paper of Zachary Chase and Shachar Lovett) related to the conjecture.
Consider the following families of subsets of
Now let .
Here are some observations:
- The number of pairs whose union is also in is .
- For every , as grows, no element belongs to more than sets in .
The first assertion holds because is exponentially larger (in a fractional power of ) than .
For the second assertion we need to show that a typical union of a pair of sets in belongs to . Note that the intersection of two random subsets of of size is and hence their union is of size . As it happens the solution of the equation is precisely our . So letting we get that a typical union of two sets from is in .
The third assertion follows from the fact that an element belongs to a fraction of sets in .
This shows that a natural stability version of Frankl’s conjecture is incorrect, and gives some hint on the appearance of the parameter .
Such a stability version is correct when we replace with . Chase and Lovett improved Gilmer’s method and proved that
Theorem: If is a -approximate union closed set system, where , then there is an element which is contained in a fraction of sets in , where
An invitation for further discussion
I will be happy to see, based on Gilmer’s paper and the five follow-up papers, a detailed, as simple as possible, explanation of Frankl’s conjecture for the parameter , to learn what is involved in Sawin’s improvement that goes beyond , and to understand the counterexamples for Gilmer’s proposal towards the full conjecture, as well as thoughts, ideas and remarks of various kind on the problem.
Links to the papers
- Justin Gilmer, A constant lower bound for the union-closed sets conjecture
- Will Sawin, An improved lower bound for the union-closed set conjecture
- Zachary Chase, Shachar Lovett, Approximate union closed conjecture
- Ryan Alweiss, Brice Huang, Mark Sellke, Improved Lower Bound for the Union-Closed Sets Conjecture
- David Ellis, Note: a counterexample to a conjecture of Gilmer which would imply the union-closed conjecture
- Luke Pebody, Extension of a Method of Gilmer
- (Dec 9.) Lei Yu, Dimension-Free Bounds for the Union-Closed Sets Conjecture