Asymptotic Enumeration of Spanning Trees via Traces and Random Walks [1/27]

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


Duration: 1:04:46
89 views
2

Methods of enumeration of spanning trees in a finite graph and relations to various areas of mathematics and physics have been investigated for more than 150 years. We will review the history and applications. Then we will give new formulas for the asymptotics of the number of spanning trees of a graph. A special case answers a question of McKay (1983) for regular graphs. The general answer involves a quantity for infinite graphs that we call ``tree entropy,



Other Videos By Microsoft Research


2016-09-05A Sample of Monte Carlo Methods in Robotics and Vision
2016-09-05Virtual Customer Environments & Customer Involvement in Innovation and Value Creation
2016-09-05Large Margin Generative Models
2016-09-05Strategies for Enhancing Ethnic and Gender Diversity in Engineering and Computer Science
2016-09-05DRM and MSFT: a product no customer wants
2016-09-05A Dynamic Pari-Mutuel Market for Hedging, Wagering, and Information Aggregation
2016-09-05Dynamic Point Samples for Free-Viewpoint Video
2016-09-05Fast Belief Propagation for Early Vision
2016-09-05Culture and Prosperity: The Truth About Markets
2016-09-05Words, links, and patterns: novel representations for Web-scale text mining
2016-09-05Asymptotic Enumeration of Spanning Trees via Traces and Random Walks [1/27]
2016-09-05Traffic Constraints Instead of Traffic Matrices: A New Approach to Traffic Characterization
2016-09-05Unknowable
2016-09-05Neighbourhood Component Analysis
2016-09-05Defying Categorization: DXARTS
2016-09-05Complex Arithmetic for Hardware Implementation: Division and Square Root
2016-09-05Distributed Implementations of Vickrey-Clarke-Groves Mechanisms
2016-09-05Not Even Wrong
2016-09-05Measurement and Monitoring in Wireless Sensor Networks
2016-09-05From TimeSync to EmStar: What's really hard in sensor networks?
2016-09-05JET: Join-Exit Tree for Time Efficient Contributory Group Key Management


Tags:
microsoft research