The entropy–KL-divergence strengthening of the union-closed sets conjecture

About 4 years old · traced to

Let AA and BB be independent identically distributed samples from a distribution supported on a family of subsets of [n][n]. Write H(A)H(A) for the entropy of AA, and D(A∪B∥A)D(A\cup B\mathbin{\|}A) for the Kullback–Leibler divergence between the distributions of A∪BA\cup B and AA. Entropy–KL strengthening. If

Pr⁡[i∈A]<0.5\Pr[i\in A]<0.5

for every i∈[n]i\in[n] and H(A)>0H(A)>0, then

H(A∪B)+D(A∪B∥A)>H(A).H(A\cup B)+D(A\cup B\mathbin{\|}A)>H(A).

The paper presents this as a sufficient strengthening that would imply the union-closed sets conjecture; it is not resolved by the paper and is therefore open.

References

Primary source

Justin Gilmer, “A constant lower bound for the union-closed sets conjecture”, arXiv:2211.09055 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.