Dedekind's problem and beyond
Connections Workshop: Extremal Combinatorics February 06, 2025 - February 07, 2025
Location: SLMath: Eisenbud Auditorium, Online/Virtual
The Dedekind’s Problem asks the number of monotone Boolean functions, a(n), on n variables. Equivalently, a(n) is the number of antichains in the n-dimensional Boolean lattice [2]^n. While the exact formula for the Dedekind number a(n) is still unknown, its asymptotic formula has been well-studied. Since any subsets of a middle layer of the Boolean lattice is an antichain, the logarithm of a(n) is trivially bounded below by the size of the middle layer. In the 1960’s, Kleitman proved that this trivial lower bound is optimal in the logarithmic scale, and the actual asymptotics was also proved by Korshunov in 1980’s. In this talk, we will discuss recent developments around Dedekind’s Problem with connection to the cluster expansion method from statistical physics. Based on joint work with Matthew Jenssen and Alex Malekshahian.