Skip to main content
SpringerLink
Log in

The Number of Linear Extensions of the Boolean Lattice

  • Published:
Order Aims and scope Submit manuscript

Abstract

Let L(Q t) denote the number of linear extensions of the t-dimensional Boolean lattice Q t. We use the entropy method of Kahn to show that

$$\frac{{\log (L(Q^t ))}}{{2^t }} = \log \left(\begin{gathered} t \hfill \\ \left| \!{\underline {\, t \,}} \right. /\left. {\underline {\, 2 \,}}\! \right| \hfill \\ \end{gathered} \right) - \frac{3} {2}\log e + o(1),$$

where the logarithms are base 2. 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 a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bollobás, B.: Combinatorics, Cambridge University Press, 1986.

  2. Bollobás, B. and Brightwell, G. R.: The number of k-SAT functions, Random Structures Algorithms 22 (2003), 227–247.

    Google Scholar 

  3. Brightwell, G. R.: The number of linear extensions of ranked posets, LSE-CDAM Research Report LSE-CDAM-2003-18, 2003.

  4. Chung, F. R. K., Frankl, P., Graham R. and Shearer, J. B.: Some intersection theorems for ordered sets and graphs, J.Combin.Theory Ser.A. 48 (1986), 23–37.

    Google Scholar 

  5. Cover, T. and Thomas, J.: Elements of Information Theory, Wiley, New York, 1991.

    Google Scholar 

  6. Csiszár, I. and Körner, J.: Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, New York, 1981.

    Google Scholar 

  7. Fishburn, P. C. and Trotter, W. T.: Linear extensions of semiorders: A maximization problem, Discrete Math. 103 (1992), 25–40.

    Google Scholar 

  8. Galvin, D. and Tetali, P.: On weighted graph homomorphisms, Special DIMACS-AMS volume on Graph Homomorphisms and Statistical Physics Models, to appear.

  9. Kahn, J.: An entropy approach to the hard-core model on bipartite graphs, Combin.Probab.Comp. 10 (2001), 219–237.

    Google Scholar 

  10. Kahn, J.: Entropy, independent sets and antichains: A new approach to Dedekind's problem, Proc.Amer.Math.Soc. 130 (2002), 371–378.

    Google Scholar 

  11. Kahn, J. and Kim, J. H.: Entropy and sorting, J.Comput.System Sci. 51 (1995), 390–399.

    Google Scholar 

  12. McEliece, R. J.: The Theory of Information and Coding, Addison-Wesley, London, 1977.

    Google Scholar 

  13. Radhakrishnan, J.: Entropy and counting, Preprint of a survey article (November 2001).

  14. Sha, J. and Kleitman, D. J.: The number of linear extensions of subset ordering, Discrete Math. 63 (1987), 271–279.

    Google Scholar 

  15. A. Shastri, Number of linear extensions of symmetric KLYM posets, Utilitas Math. 53 (1998), 25–35.

    Google Scholar 

  16. Shepp, L. A.: The FKG inequality and some monotonicity properties of partial orders, SIAM J.Algebraic Discrete Methods 1 (1980), 295–299.

    Google Scholar 

  17. Shepp, L.: The XYZ conjecture and the FKG inequality, Ann.Probab. 10 (1982), 824–827.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, London School of Economics, Houghton St., London, WC2A 2AE, England

    Graham R. Brightwell

  2. School of Mathematics & College of Computing, Georgia Tech., Atlanta, GA, 30332-0160, U.S.A.

    Prasad Tetali

Authors
  1. Graham R. Brightwell
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Prasad Tetali
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brightwell, G.R., Tetali, P. The Number of Linear Extensions of the Boolean Lattice. Order 20, 333–345 (2003). https://doi.org/10.1023/B:ORDE.0000034596.50352.f7

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:ORDE.0000034596.50352.f7

Keywords

Search

Navigation