Date
Mon September 23rd 2024, 4:00pm
Location
Sequoia 200
Speaker
Persi Diaconis, Stanford Math and Statistics
Trees are everywhere in applied probability and computer science. It is natural to ask about what a typical tree looks like. I will review a surprisingly large literature. For example, Cayley's theorem tells us there are n^(n-2) labeled trees and it's easy to work with them. There is no similar formula for unlabeled trees and the math is harder. I'll introduce a new algorithm (the Burnside process) for generating random unlabeled trees and use it to show real discrepancies between asymptotic theory and ''reality''. Of course, there are many flavors of trees and many open problems.
This is joint work with Laurent Bartholdi.