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

Watch on YouTube

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

More from this channel