Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR22-168 | 28th November 2022 03:05

A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture

RSS-Feed




Revision #2
Authors: Zubayir Kazi
Accepted on: 28th November 2022 03:05
Downloads: 218
Keywords: 


Abstract:

Abstract The Union Closed Set Conjecture states that if a set system X, a subset of {P}([n]) is closed under pairwise unions, then there exists a\in[n] in at least half of the sets of X. We show that there is a very natural generalization of the union closed set conjecture which gives a lower bound for k-set subsets of [n]. This a stronger version of a Conjecture of (Nagel, 2022). We then prove the Conjecture conditional on the Union Closed Set Conjecture using invariants of Union-Closed sets. Additionally, we prove that there exists a k-set in .38^{k}|F| sets of a union closed set X for every n+1 > k > 0 using the recent improvements in (Gilmer, 2022), (Sawin, 2022), (Alweiss et al, 2022), (Lovett et al, 2022). We explain why our result suggests a lack of sharpness of the original conjecture.



Changes to previous version:

Heavy rewriting of proofs and reorganizing.
Correction of typing errors.


Revision #1 to TR22-168 | 24th November 2022 17:13

A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture





Revision #1
Authors: Zubayir Kazi
Accepted on: 24th November 2022 17:13
Downloads: 303
Keywords: 


Abstract:

Abstract The Union Closed Set Conjecture states that if a set system X\subseteq\mathcal{P}([n]) is closed under pairwise unions, then there exists a\in[n] in at least half of the sets of X. We show that there is a very natural generalization of the union closed set conjecture which gives a lower bound for k-set subsets of [n]. This a stronger version of a Conjecture of (Nagel, 2022). We then prove the Conjecture conditional on the Union Closed Set Conjecture using invariants of Union-Closed sets. Additionally, we prove that there exists a k-set in .38^{k}|F| sets of a union closed set X for every n\geq k>0 using the recent improvements in (Gilmer, 2022) and (Alweiss et al, 2022). We explain why our result suggests a lack of sharpness of the original conjecture.



Changes to previous version:

Fixed typos, fixed orderings


Paper:

TR22-168 | 23rd November 2022 22:52

A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture





TR22-168
Authors: Zubayir Kazi
Publication: 24th November 2022 12:14
Downloads: 398
Keywords: 


Abstract:

Abstract The Union Closed Set Conjecture states that if a set system X\subseteq\mathcal{P}([n]) is closed under pairwise unions, then there exists a\in[n] in at least half of the sets of X. We show that there is a very natural generalization of the union closed set conjecture which gives a lower bound for k-set subsets of [n]. This a stronger version of a Conjecture of (Nagel, 2022). We then prove the Conjecture conditional on the Union Closed Set Conjecture using invariants of Union-Closed sets. Additionally, we prove that there exists a k-set in .38^{k}|F| sets of a union closed set X for every n\geq k>0 using the recent improvements in (Gilmer, 2022) and (Alweiss et al, 2022). We explain why our result suggests a lack of sharpness of the original conjecture.



ISSN 1433-8092 | Imprint