Random Graphs

Module MA5208

This Module is offered by TUM Department of Mathematics.

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 workloadContact hoursCredits (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.

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.

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.

Module Exam

Description of exams and course work

Klausur oder mündliche Prüfung (abhängig von der Teilnehmerzahl)

Exam Repetition

There is a possibility to take the exam at the end of the semester.

Condensed Matter

When atoms interact things can get interesting. Fundamental research on the underlying properties of materials and nanostructures and exploration of the potential they provide for applications.

Nuclei, Particles, Astrophysics

A journey of discovery to understanding our world at the subatomic scale, from the nuclei inside atoms down to the most elementary building blocks of matter. Are you ready for the adventure?

Biophysics

Biological systems, from proteins to living cells and organisms, obey physical principles. Our research groups in biophysics shape one of Germany's largest scientific clusters in this area.