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

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(ABA)D(A\cup B\mathbin{\|}A) for the Kullback–Leibler divergence between the distributions of ABA\cup B and AA. Entropy–KL strengthening. If

Pr[iA]<0.5\Pr[i\in A]<0.5

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

H(AB)+D(ABA)>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.

Sources & referencesView supporting material

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.