On Dedekind's problem, a sparse version of Sperner's theorem, and antichains of a given size in the Boolean lattice

2024/11/05 by Matthew Jenssen, Alexandru Malekshahian, Jenssen, Matthew +3 · 2 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2411.03400

Abstract

Dedekind's problem, dating back to 1897, asks for the total number ψ(n) of antichains contained in the Boolean lattice B_n on n elements. We study Dedekind's problem using a recently developed method based on the cluster expansion from statistical physics and as a result, obtain several new results on the number and typical structure of antichains in B_n. We obtain detailed estimates for both ψ(n) and the number of antichains of size β\binomn\lfloor n/2 \rfloor for any fixed β>0. We also establish a sparse version of Sperner's theorem: we determine the sharp threshold and scaling window for the property that almost every antichain of size m is contained in a middle layer of B_n.

Cited by

• Asymptotic enumeration via graph containers and entropy
• Finite-n Estimate of Dedekind Numbers by Layer-Ratio Monte Carlo

Related

• A sharp threshold for a random version of Sperner's Theorem
• Solving systems of equations on antichains for the computation of the ninth Dedekind Number
• Intervals of Antichains and Their Decompositions
• On the number of antichains of sets in a finite universe
• Applications of graph containers in the Boolean lattice