Random Graphs
Module MA5208
This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
Basic Information
MA5208 is a semester module in English language at Master’s level which is offered irregular.
This module description is valid from SS 2012 to SS 2012.
| Total workload | Contact hours | Credits (ECTS) |
|---|---|---|
| 150 h | 45 h | 5 CP |
Content, Learning Outcome and Preconditions
Content
Although random graphs were first considered as a mere tool for proving the existence of graphs with seemingly contradictory properties, they now form a field of study in their own right. In many cases, they provide appropriate models for real-world networks, and the investigation of their typical properties then lay the foundation for the average-case analysis of many algorithms in optimization.
In this course we first focus on the binomial G(n,p) model and investigate some of the phase transitions in its evolution. We then switch to more complicated models for constrained random graphs, such as random trees and random regular graphs. Finally, we analyse randomized algorithms and the expected performance of deterministic algorithms for several optimization problems.
The underlying probabilistic methods comprise: First and Second Moment, Large Deviation Inequalities, Generating Functions, Markov Chains.
In this course we first focus on the binomial G(n,p) model and investigate some of the phase transitions in its evolution. We then switch to more complicated models for constrained random graphs, such as random trees and random regular graphs. Finally, we analyse randomized algorithms and the expected performance of deterministic algorithms for several optimization problems.
The underlying probabilistic methods comprise: First and Second Moment, Large Deviation Inequalities, Generating Functions, Markov Chains.
Learning Outcome
At the end of the module, students have understood different models of random graphs. They can apply various probabilistic methods to determine typical properties of these random graphs.
They are able to use these properties to design and analyse the performance of algorithms for some of the classical optimization problems.
They are able to use these properties to design and analyse the performance of algorithms for some of the classical optimization problems.
Preconditions
MA1001 Analysis 1, MA1002 Analysis 2, MA1101 Linear Algebra 1, MA1102 Linear Algebra 2, MA1401 Introduction to Probability, MA1501 Introduction to Discrete Mathematics, MA2501 Algorithmic Discrete Mathematics
Courses, Learning and Teaching Methods and Literature
Learning and Teaching Methods
Lectures on the blackboard, exercises for work during the tutorials and for homework.
Media
Blackboard
Literature
N. Alon and J. Spencer: The Probabilistic Method. Wiley, 2011.
B. Bollobas: Random Graphs. Cambridge University Press, 2001.
P. Flajolet and R. Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009.
S. Janson, T. Luczak, and A. Rucinski: Random Graphs. Wiley, 2000.
R. Motwani and P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
B. Bollobas: Random Graphs. Cambridge University Press, 2001.
P. Flajolet and R. Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009.
S. Janson, T. Luczak, and A. Rucinski: Random Graphs. Wiley, 2000.
R. Motwani and P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.