2nd degree (Master)
Dr. Ori Gurel-Gurevich
Coordinator Office Hours:
Prof Ori Gurel-Gurevich
A uniform spanning tree (UST) is a random spanning tree, chosen uniformly at random from all spanning trees of a given finite graph. We will see how to simulate such a tree, what are its properties and how to generalize this notion to infinite graphs.
Learning outcomes - On successful completion of this module, students should be able to:
understand what are uniform spanning trees and forests.
know when a simple random walk on a graph is recurrent or transient.
understand open problems in this topic.
Teaching arrangement and method of instruction:
Random walks and electric networks.
Uniform spanning tree of a finite graph.
Infinite electrical networks.
Uniform spanning forests of an infinite graph.
Probability on Trees and Networks by Lyons and Peres, chapters 2,3,4,9,10
Additional Reading Material:
End of year written/oral examination 0 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 100 %
Assignments 0 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %