REVIEW 4 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
A constant lower bound for the union-closed sets conjecture
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 4 Pith papers
-
Redundancy Is All You Need (for CSP Sparsification)
For any CSP predicate R, unweighted CSP(R) instances admit sparsifiers of size at most their non-redundancy (up to polylog factors); weighted cases are pinned to chain length, via a VC-type theorem for set families us...
-
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.
-
Multiplicative error set system sparsification: A simpler proof via chain length contraction
Chain length characterizes multiplicative sparsifiability of set systems, shown via a generalized contraction algorithm that simplifies earlier proofs.
-
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)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.