The Number of Linear Extensions of the Boolean Lattice
438 views · Published 6 September 2016 · 1:11:20 · Indexed 22 October 2026
Channel: Microsoft Research · 2016 · Science & Technology
Let L(Q^t) denote the number of linear extensions of the t-dimensional Boolean lattice Q^t, for t>1. We use an entropy technique of J. Kahn to show that log(L(Q^t))/2^t = log{t choose t/2} - (3/2)log e + o(1), where the logarithms are base 2, and o(1) goes to zero as t goes to infinity. We also find the exact maximum number of linear extensions of a d-regular bipartite order on n elements, in the case when n is a multiple of 2d. This is joint work with Graham Brightwell (London School of Economics).