Course Information

Lecturers:

Professor Nick Wormald & Dr Jane Gao, Monash University

Synopsis:

The probabilistic method proves the existence of a mathematical structure by showing a random element in an appropriate probability space has the desired properties with positive probability. This might sound simple enough, but books have been written on techniques inspired by the idea. A graph is a combinatorial structure consisting of nodes (vertices) with lines or edges joining them.

The course will introduce some basic techniques of the probabilistic method and give applications in graph theory and combinatorics. In particular, the probabilistic method gives easy proofs of the existence of some graphs (and other objects) which are very hard to construct explicitly, or not known to exist by other methods.

The course will also study random graphs –  graphs selected at random from some given probability space. Some appealing properties of these graphs can be proved. They can also be woven into uses of the probabilistic method. Additionally, the methods studied here can give rise to some surprisingly simple and efficient computer algorithms.

Topics to be covered include the following:

  • Linearity of expectation and alterations;
  • The second moment method; Random graph models and properties;
  • The local lemma;
  • Martingales and concentration inequalities;
  • Branching processes and the size of the giant component;
  • Method of moments and random regular graphs;
  • Randomised algorithms and derandomization.

Contact hours:

TBA

Prerequisites:

Knowledge of mathematics after first year will not be assumed, but some things would be very useful: knowledge of discrete probability (binomial, normal and Poisson distributions, basic properties of expectation and variance); revision of limits and Taylor polynomials; familiarity with O() and o() notation is also an advantage.

Resources:

  • “The Probabilistic Method”, by N. Alon and J. Spencer
  • “Introduction to Random Graphs” by A. Frieze and M. Karonski

Additional lecture notes will be supplied.

Lecturer Biographies

Probabilistic methods and random graphs

Professor Nicholas Wormald, Monash University

Nick Wormald is an Australian Laureate Fellow, and Professor of Mathematics at Monash University. Prior to that, he held appointments at University of Waterloo, Louisiana State University, then Universities of Newcastle, Auckland, Melbourne, and again Waterloo as a tier 1 Canada Research Chair.

Nick specialises in  random graphs and probabilistic combinatorics, graph theory, enumeration, the analysis of graph algorithms, Steiner trees, the analysis of real-life networks, and other areas in combinatorics, as well as the optimisation of underground mine access networks. See http://users.monash.edu.au/~nwormald/ for more detail.

Probabilistic methods and random graphs

Dr Jane Gao, Monash University

Dr Jane Gao is an Australian Research Council DECRA Fellow, and Lecturer at Monash University. Prior to that, she was a Research Assistant Professor at University of Waterloo in Canada.

Jane’s research focuses on properties and generation of random structures such as random graphs. The theory of random graphs and random graph generation has applications to modern networks such as social networks and those occurring in statistical physics applications.
More information is available on her webpage: http://users.monash.edu/~gaojan/

Contact Us

We're not around right now. But you can send us an email and we'll get back to you, asap.

Not readable? Change text.