Kahn's equal-size upward-closed systems conjecture

About 1 year old · traced to 2025

Let $Q_n$ be the power set of $[n]=\{1,2,\dots,n\}$ ordered by inclusion, and let $X,Y,Z\subset Q_n$ be upward closed set systems of equal size. Define the set of points belonging to exactly one of the three systems by

S_1=(X\cap Y^c\cap Z^c)\sqcup (X^c\cap Y\cap Z^c)\sqcup (X^c\cap Y^c\cap Z).

Kahn's conjecture. If $|X|=|Y|=|Z|$ , then

\frac{|S_1|}{2^n}\le \frac49.

The conjecture is motivated by the product construction for three independent upward-closed systems. The source gives an upper bound of $3\rho(1-\rho)/(1+\rho)$ for equal-sized systems and notes that the conjectured bound is false in the preceding stronger formulation for $n=5$ ; it does not state whether this equal-size formulation is resolved.

References

Primary source

Kada Williams, “A Correlation Inequality on Three Functions”, arXiv:2502.14857 (2025).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A 2025 preprint claims a counterexample, and an unverified posted attempt points to it.

Kahn’s conjecture asks whether three equal-sized upward-closed systems in $Q_n$ can have exactly-one density above $4/9$ . Kada Williams’s 2025 preprint says yes, answering the question negatively.

Known results

Williams records the upper bound $3\rho(1-\rho)/(1+\rho)$ for equal-density systems and notes that the stronger bound $3\rho(1-\rho)^2$ already fails for $n=5$ ; this is distinct from Kahn’s conjecture.

February 2025 counterexample claim

Williams claims an explicit construction in dimension $n=21$ , with all three densities equal to $3/8$ and exactly-one density greater than $0.447>4/9$ . The construction lifts a weighted-cube example from dimension $7$ ; no independent verification or retraction appears in the retrieved record.

Posted attempt

An unverified posted attempt identifies Williams’s preprint as a complete disproof; it supplies no independently checked argument.

Current status (as of August 2026): Williams’s preprint claims to disprove the conjecture in dimension $21$ , but the retrieved record does not independently verify the counterexample, so the conjecture is not settled.

Sources

CounterexampleThis solution needs a summarySee full solutionHide full solution

Disproven by Kada Williams in 2025, see "A Correlation Inequality on Three Functions" (https://doi.org/10.48550/arXiv.2502.14857).