The Number of Linear Extensions of the Boolean Lattice

Опубликовано 6 сентября 2016, 21:24

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).