MTH 692   Special Topics II:   Probability on Discrete Structures

Spring 2009

Instructor: Lubos Thoma                   Email:
Office: Lippitt Hall 102H Tel: 874.4451

 Class schedule: TR 12.30 -- 1.45pm, Lippitt Hall 201
 Office hours: TR 10.00am and by appointment

Description:   This is a new graduate topics class offered in our program. The purpose of the course is to present the fundamental concepts and techniques of the probabilistic method. The class will include topics such as random graphs and networks, phase transitions, random walks and matrices, randomized algorithms, percolation, and pseudorandomness.

Topics covered:     692topics.pdf

Textbook:     N. Alon, J. Spencer: The probabilistic method, Wiley

Additional texts:
      J. Matousek, J. Vondrak: The probabilistic method
      S. Janson, T. Luczak, A. Rucinski: Random graphs, Wiley
      B. Bollobas, Random Graphs, Cambridge Univ. Press
      M. Molloy, B. Reed: Graph Colouring and the Probabilistic Method
      M. Mitzenmacher, E. Upfal, Probability and Computing - Randomized Algorithms and Probabilistic Analysis, Cambridge Univ. Press
      Penrose: Random geometric graphs

Accommodations: Students who require accommodations and who have documentation from Disability Services (874-2098) should make arrangements with me as soon as possible.