The Number of Linear Extensions of the Boolean Lattice

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=bjUqDyxc8f4


Duration: 1:11:20
350 views
0

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



Other Videos By Microsoft Research


2016-09-06eScience Workshop 2005 - DopplerSource: .NET Framework for Accesing Doppler Radar Data
2016-09-06eScience Workshop 2005 - Bio-Workflow Using Biztalk
2016-09-06Microsoft Research Faculty Summit 2005 — Computer Science Research Agenda in Latin America
2016-09-06MIT iCampus: Disseminating Innovations, Sharing Technology, Building Community
2016-09-06WACE 2005 - Inter-Partition Networking, a Hybrid Network Platform for Collaborative Applications
2016-09-06The Giant Component
2016-09-06Exact 2-CSP Optimization Using Matrix Multiplication
2016-09-06TechFest - Applications of Automated Reasoning
2016-09-06Automatizability and Learnability
2016-09-06On the measure of intersecting families, spectral methods
2016-09-06The Number of Linear Extensions of the Boolean Lattice
2016-09-06Abelian surfaces with a given number of points
2016-09-06Rapt: Attention and the Focused Life
2016-09-06A brief synopsis of recent research at Multimedia Communications and Systems Lab
2016-09-06The End of Alchemy: Empirical Software Security Assurance
2016-09-06Partially Observable Markov Decision Processes for Spoken Dialogue Systems
2016-09-06Technical Presentations
2016-09-06The Posthuman Dada Guide: Tzara and Lenin Play Chess
2016-09-06Hit the Ground Running: A Manual for New Leaders
2016-09-06Interprocedural Analysis and the Verification of Concurrent Programs
2016-09-06Putting our digital information in its place


Tags:
microsoft research