Union closed sets conjecture
Description of constant
$C_{6}$ is the largest constant such that any union-closed family of sets on an $N$-element ground set has an element contained in at least $C_{6}$ fraction of the sets.
Known upper bounds
| Bound |
Reference |
Comments |
| $1/2 = 0.5$ |
[F1995] |
Conjectured (in 1976) to be optimal |
Known lower bounds
| Bound |
Reference |
Comments |
| $0$ |
Trivial |
|
| $0.1$ |
[G2022] |
|
| $(3-\sqrt{5})/2 = 0.381966\dots$ |
[AHS2022], [CL2022], [P2022], [S2022] |
|
| $>(3-\sqrt{5})/2$ |
[S2022] |
|
| $0.38234$ |
[C2022], [Y2022] |
|
| $0.38271$ |
[L2023] |
|
References
- [AHS2022] Alweiss, Ryan; Huang, Brice; Sellke, Mark. Improved lower bound for the union-closed sets conjecture. arXiv preprint arXiv:2211.11731, 2022.
- [BS2015] Bruhn, Henning; Schaudt, Oliver. The journey of the union-closed sets conjecture. Graphs and Combinatorics, 31(6):2043-2074, 2015.
- [C2022] Cambie, Stijn. Better bounds for the union-closed sets conjecture using the entropy approach. arXiv preprint arXiv:2212.12500, 2022.
- [CL2022] Chase, Zachary; Lovett, Shachar. Approximate union closed conjecture. arXiv preprint arXiv:2211.11689, 2022.
- [F1995] Frankl, Péter. Extremal set systems. Handbook of combinatorics, 2:1293-1329, 1995.
- [G2022] Gilmer, Justin. A constant lower bound for the union-closed sets conjecture. arxiv:2211.09055, 2022.
- [L2023] Liu, Jingbo. Improving the Lower Bound for the Union-closed Sets Conjecture via Conditionally IID Coupling. arXiv preprint arXiv:2306.08824, 2023.
- [P2022] Pebody, Luke. Extension of a method of Gilmer. arXiv preprint arXiv:2211.13139, 2022.
- [S2022] Sawin, Will. An improved lower bound for the union-closed set conjecture. arXiv preprint arXiv:2211.11504, 2022.
- [Y2022] Yu, Lei. Dimension-Free Bounds for the Union-Closed Sets Conjecture. arXiv preprint arXiv:2212.00658, 2022.