A Nice Example Related to the Frankl Conjecture

Combinatorics and more 2022-11-30

The example

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.

Let $\psi=\frac {3+\sqrt 5}{2} = 0.38..$

Consider the following families of subsets of $[n]$

${\cal F}_1=\{S \subset [n]: |S|=\psi n + n^{2/3}\}$ , and

${\cal F}_2 = \{ T \subset [n]: |T|>(1-\psi) n \}$ .

Now let ${\cal F}={\cal F}_1 \cup {\cal F}_2$ .

Here are some observations:

$|{\cal F}_2| = o(|{\cal F}_1|)$ .
The number of pairs $(S,T):S,T \in {\cal F}$ whose union is also in ${\cal F}$ is $(1-o(1)) {|\cal F}|^2$ .
For every $\epsilon >0$ , as $n$ grows, no element $k \in [n]$ belongs to more than $(\psi+\epsilon) |{\cal F}|$ sets in ${\cal F}$ .

The first assertion holds because ${{n} \choose {\psi n +n^{2/3}}}$ is exponentially larger (in a fractional power of $n$ ) than ${{n} \choose {(1-\psi )n}}$ .

For the second assertion we need to show that a typical union of a pair of sets in ${\cal F}_1$ belongs to ${\cal F}_2$ . Note that the intersection of two random subsets of $[n]$ of size $\phi n$ is $\phi ^2 n$ and hence their union is of size $2\phi - \phi^2$ . As it happens the solution of the equation $2\phi-\phi^2 = 1-\phi$ is precisely our $\psi=\frac {3+\sqrt 5}{2}$ . So letting $\phi=\psi + n^{-1/3}$ we get that a typical union of two sets from ${\cal F}_1$ is in ${\cal F}_2$ .

The third assertion follows from the fact that an element $k \in [n]$ belongs to a fraction of $\psi + n^{-1/3}$ sets in ${\cal F}_1$ .

This shows that a natural stability version of Frankl’s conjecture is incorrect, and gives some hint on the appearance of the parameter $\psi$ .

Stability result

Such a stability version is correct when we replace $1/2$ with $\psi$ . Chase and Lovett improved Gilmer’s method and proved that

Theorem: If $\cal F$ is a $(1-\epsilon)$ -approximate union closed set system, where $\epsilon <1/2$ , then there is an element which is contained in a $(\psi-\delta)$ fraction of sets in $\cal F$ , where

$\delta=2\epsilon (1+\frac {\log (1/\epsilon)}{\log |{\cal F}|}).$

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 $\psi$ , to learn what is involved in Sawin’s improvement that goes beyond $\psi$ , 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