The Hebrew University Logo
close window close
PDF version
Last update 07-03-2016
HU Credits: 2

Degree/Cycle: 2nd degree (Master)

Responsible Department: Mathematics

Semester: 1st Semester

Teaching Languages: Hebrew

Campus: E. Safra

Course/Module Coordinator: Dr. Ori Gurel-Gurevich

Coordinator Office Hours: by appointment

Teaching Staff:
Prof Ori Gurel-Gurevich

Course/Module description:
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.

Course/Module aims:

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.

Attendance requirements(%):

Teaching arrangement and method of instruction: lecture

Course/Module Content:
Random walks and electric networks.
Uniform spanning tree of a finite graph.
Wilson's algorithm.
Infinite electrical networks.
Uniform spanning forests of an infinite graph.

Required Reading:
Probability on Trees and Networks by Lyons and Peres, chapters 2,3,4,9,10

Additional Reading Material:

Course/Module evaluation:
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 %

Additional information:
Students needing academic accommodations based on a disability should contact the Center for Diagnosis and Support of Students with Learning Disabilities, or the Office for Students with Disabilities, as early as possible, to discuss and coordinate accommodations, based on relevant documentation.
For further information, please visit the site of the Dean of Students Office.