Random walks and percolation on graphs
Project Description
The investigation of stochastic models associated with graphs has been subject of much interest over the last several decades. This project aims at developing tools to analyze two such models: random walks and percolation theory. The former model deals with the study of random motions on fixed graphs, while the latter consists of the study of the random removal of edges or vertices in such graphs with the goal of understanding the remaining structure.
Natural questions are then to characterize the long-term behavior of random walks on various graphs on one hand, or the emergence of large connected components in associated percolation processes on graphs on the other. A main theme in this direction is the utilization of profound connections to the theory of electric networks, discrete potential theory, branching processes, and group theory.
During this project, a number of such fundamental connections will be explored in detail.
Natural questions are then to characterize the long-term behavior of random walks on various graphs on one hand, or the emergence of large connected components in associated percolation processes on graphs on the other. A main theme in this direction is the utilization of profound connections to the theory of electric networks, discrete potential theory, branching processes, and group theory.
During this project, a number of such fundamental connections will be explored in detail.
Supervisor
NITZSCHNER, Maximilian Alexander
Quota
1
Course type
UROP1000
UROP1100
UROP2100
UROP3100
UROP4100
Applicant's Roles
This project targets undergraduate students who are interested in various aspects of discrete probability theory. Prior exposure to some fundamental techniques in probability theory is helpful but not strictly required for successful participation in this project. A solid foundation on elementary analysis and linear algebra is strongly suggested. At the end of the project, students in UROP 1100 should be able to write an expository article containing known proofs in the area. For students in UROP 2100 or higher, students are expected to apply the discussed techniques to investigate models that are subject of current research.
Applicant's Learning Objectives
Upon successful participation in this project, students will
1) deepen their knowledge in the broader area of probability theory and learn fundamental techniques that are used in discrete probability theory;
2) be able to identify current themes and trends in research on random walks and percolation theory and read original research papers in these fields;
3) have the opportunity to tackle some elementary to moderate open problems.
1) deepen their knowledge in the broader area of probability theory and learn fundamental techniques that are used in discrete probability theory;
2) be able to identify current themes and trends in research on random walks and percolation theory and read original research papers in these fields;
3) have the opportunity to tackle some elementary to moderate open problems.
Complexity of the project
Moderate