ECCC-Report TR22-168https://eccc.weizmann.ac.il/report/2022/168Comments and Revisions published for TR22-168en-usMon, 28 Nov 2022 03:05:15 +0200
Revision 2
| A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture |
Zubayir Kazi
https://eccc.weizmann.ac.il/report/2022/168#revision2Abstract 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.Mon, 28 Nov 2022 03:05:15 +0200https://eccc.weizmann.ac.il/report/2022/168#revision2
Revision 1
| A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture |
Zubayir Kazi
https://eccc.weizmann.ac.il/report/2022/168#revision1Abstract 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.Thu, 24 Nov 2022 17:13:47 +0200https://eccc.weizmann.ac.il/report/2022/168#revision1
Paper TR22-168
| A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture |
Zubayir Kazi
https://eccc.weizmann.ac.il/report/2022/168Abstract 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.Thu, 24 Nov 2022 12:14:14 +0200https://eccc.weizmann.ac.il/report/2022/168