REVIEW 5 cited by
A constant lower bound for the union-closed sets conjecture
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We show that for any union-closed family $\mathcal{F} \subseteq 2^{[n]}, \mathcal{F} \neq \{\emptyset\}$, there exists an $i \in [n]$ which is contained in a $0.01$ fraction of the sets in $\mathcal{F}$. This is the first known constant lower bound, and improves upon the $\Omega(\log_2(|\mathcal{F}|)^{-1})$ bounds of Knill and W\'{o}jick. Our result follows from an information theoretic strengthening of the conjecture. Specifically, we show that if $A, B$ are independent samples from a distribution over subsets of $[n]$ such that $Pr[i \in A] < 0.01$ for all $i$ and $H(A) > 0$, then $H(A \cup B) > H(A)$.
Forward citations
Cited by 5 Pith papers
-
Frequent elements in union-closed set families
The k-th most frequent element in any union-closed set family appears in at least 1/(2^{k-1}+1) of the sets, with equality only for the near-k-cube families.
-
A lemma on a finite union-closed family of finite sets and its applications
A lemma bounding element frequencies under deletion implies the equivalence of Frankl's conjecture and Nagel's conjecture, and strengthens a bound of Nagel for sets of size at least two.
-
Supersaturation in union-closed families of sets
Union-closed supersaturation: fixed-size union-closed families minimize k-chains exactly when they are top-aligned, with uniqueness for m>n and positive minimum.
-
Entropy approach for a generalization of Frankl's conjecture
A set family has an element in at least half its sets if and only if there exists an auxiliary family G satisfying an entropy inequality, giving a new equivalent form of Frankl's conjecture.
-
Entropy methods in combinatorics
A selective survey of entropy methods in combinatorics, detailing randomized chain rules, Shearer's inequality, random homomorphisms, Pinsker-type arguments, the union-closed sets breakthrough, and entropy approaches ...
Discussion (0). Continue with ORCID to comment.