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

CREATORGennian Ge, Jialuo Wang, Zixiang Xu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41095
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18948

Browse the full library · About the Tower of Babel