[Combinatorics] Breaking the Barrier: Improving the Erdős-Kleitman Conjecture via KKL Theorem

TL;DR

The Erdős-Kleitman conjecture has been a persistent enigma in extremal set theory for 50 years. While 2018 saw a massive breakthrough reaching a $(1-1/s)2^n$ lower bound, this new paper by Ge, Wang, and Xu pushes the frontier even further. By elegantly linking the structure of s-saturated families to the influences of Boolean functions via the KKL Theorem, the authors introduce an $n$-dependent improvement that challenges the limits of current analytical methods.

Background: The Saturation Tension

In the world of set systems, a family $\mathcal{F}$ is s-saturated if:

1. It contains no $s$ pairwise disjoint sets (no matching of size $s$).
2. It is maximal: adding any set to $\mathcal{F}$ would create an $s$-matching.

The conjecture suggests these families are quite dense, specifically $|\mathcal{F}|⩾(1-2^{-(s-1)})\cdot 2^n$. Until recently, even proving $|\mathcal{F}|⩾(1/2+ϵ)2^n$ was considered a "difficult problem."

The Mathematical Intuition: Why Boolean Influence?

The authors build upon a critical insight from Bucić et al. (2018): an $s$-saturated family is increasing (upward-closed), and its complement is exactly the disjoint occurrence of $(s-1)$ copies of itself.

The core of the new method lies in Influence. In the analysis of Boolean functions, the influence of a variable measures how often flipping that variable flips the output. The Kahn-Kalai-Linial (KKL) Theorem guarantees that at least one variable has an influence of at least $\Omega (p\log n/n)$, where $p$ is the density of the function.

By treating a set family as a Boolean function, the authors use KKL to find a specific "direction" in the discrete cube where the family's density is slightly "lopsided." This lopsidedness is exactly what allows them to squeeze more out of the existing correlation inequalities.

Methodology: The Architecture of the Proof

The proof strategy follows two distinct paths:

1. The Correlation Path (Primary): Uses the KKL Theorem to bound the size of sections of the family.
2. The Algebraic Path (Secondary): Refines the polynomial method by introducing a "combinatorial twist."

Key Formula: The Main Improvement

The authors prove:

This formula shows that as the dimension $n$ grows, the lower bound increases relative to the previous $1-1/s$ baseline.

Breaking Down the Algebraic Refinement

In Section 4, the authors define $g(n,s)$ as a specific threshold and improve the bound by an additional exponential term based on the dimension of the span of specific polynomials ($W_k$).

Experiments and Results: Pushing the SOTA

The improvement is measured purely in terms of the mathematical lower bound.

• Previous SOTA (2018): $1-1/s$
• This Work: $1-1/(s+extcorrectionfactor)$

The "correction factor" $(s-2)\frac{\log n}{2\sqrt{5}n}$ essentially means that as the complexity of the space ($n$) increases, we can guarantee a larger portion of the hypercube belongs to the saturated family.

In the concluding remarks, the authors analyze the limit of this ratio, proving that while the KKL method is powerful, it has a natural boundary.

Critical Insight & Limitations

The most striking part of the paper is Proposition 5.1. The authors construct a specific $s$-saturated family where the "atypically small section" disappears in the limit ($no\infty$).

The Takeaway: This implies that the $\frac{\log n}{n}$ improvement is likely the maximal possible gain one can get using only general Boolean function properties. To reach the full Erdős-Kleitman conjecture, researchers will need to exploit "finer features" of set saturation that are not captured by volume or influence alone.

Conclusion

This paper is a masterclass in cross-disciplinary mathematics. By importing tools from theoretical computer science (Boolean analysis) into extremal combinatorics, the authors have provided the most significant update to the Erdős-Kleitman problem since 2018, while simultaneously defining the "ceiling" for this specific technical approach.