TOPICS
Search

Daykin-Frankl Conjecture


The Daykin-Frankl conjecture (Daykin and Frankl 1983) asserts that a family that is an order-convex set P in the Boolean lattice Q_n of subsets of an n-element set has partial order width at least the same fraction of its size as the partial order width of Q_n is of 2^n. Writing w(P) for the largest size of an antichain in P, the assertion is

 w(P)>=(|P|)/(2^n)(n; |_n/2_|),

where |_x_| is the floor function. For the whole Boolean lattice this becomes equality by Sperner's theorem. For an antichain it is immediate because w(P)=|P|.

Williams (2026) reported a proof, together with the stronger product inequality

 w(P×Q_k)>=(|P|)/(2^n)w(Q_(n+k)).

The proof was obtained with GPT-5.6 Sol and checked and written up by Williams. Independent external verification had not been reported as of Sep. 7, 2026.


See also

Antichain, Boolean Lattice, Order-Convex Set, Partial Order Width, Sperner's Theorem

Explore with Wolfram|Alpha

References

Daykin, D. E. and Frankl, P. "Inequalities for Subsets of a Set and KLYM Posets." SIAM J. Algebraic Discrete Methods 4, 67-69, 1983.Williams, K. K. "Confirmation of the Daykin-Frankl Conjecture." 2 Sep 2026. https://arxiv.org/abs/2609.03087.

Cite this as:

Weisstein, Eric W. "Daykin-Frankl Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Daykin-FranklConjecture.html

Subject classifications