Professor Nick Wormald & Dr Jane Gao, Monash University
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.
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.
- “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.
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.
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/