Improvement on the Erdős-Kleitman conjecture via the KKL theorem
Gennian Ge, Jialuo Wang, Zixiang Xu · 2026
Read Improvement on the Erdős-Kleitman conjecture via the KKL theorem by Gennian Ge, Jialuo Wang, Zixiang Xu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18948.txt.
Description
Ge and co-authors improve a long-standing guess by Erdos and Kleitman on large set families with no matching of a set size. For decades, the best broad lower bound stayed at a plain half of all sets. A 2018 result pushed the bound higher with two elegant proofs. Their new bound edges a bit higher still. The gain comes from a link to a classic result on how Boolean functions respond to input flips. A weaker gain also comes from linear algebra with a twist.
Catalog record
| CREATOR | Gennian Ge, Jialuo Wang, Zixiang Xu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41095 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.18948