Discrete Probability (MA40239)
Semester II 2017-18
Lecturers
Mathew Penrose and Florian Völlering
Content:
Random Graphs: definition and motivation; small subgraphs; giant component and phase transition; maximum degree; clique number. Other aspects of random graphs such as: connectivity, chromatic number, bipartite matchings, sharp thresholds.
Percolation Theory: non-triviality of the phase transition; lattice animals, percolation on trees, uniqueness of the infinite component, properties and interpretation of the percolation probability. Other aspects of percolation theory such as: the critical value on the square lattice, self-avoiding walk, random resistor networks.
Further topics in discrete probability may be considered such as: invariant distributions, bounds and cut-off phenomena for Markov chain mixing times and examples thereof; entropy, noiseless coding, discrete memoryless channel in information theory.
Books
- Grimmett : Probability on Graphs
- Alon and Spencer: The Probabilistic Method
- Bollobas: Random Graphs
- Grimmett : Percolation
- Frieze and Karonski: Introduction to random graphs
(may be available online)
News
-
Week 6: Florian is taking over the course at this point
(from March 12), starting from Chapter 6.
-
There is a course folder in the department
pigeonholes. To get feedback
on problem sheet 3, please leave your work there.
-
Wednesday 21 February. This was mainly a `lecture' rather
than a `problems class'. Got to the end of proof of
Theorem 4.5.
Solutions to
Sheet 2 are available below - suggest to go through these
on your own.
Lecture notes.
- Pages 1-8 (Section 1). pdf file.
- Pages 9-14 (Section 2). pdf file.
- Pages 15-17 (Section 3). pdf file.
- Pages 18-22 (Section 4). pdf file.
- Pages 23-26 (Section 5). pdf file.
- Pages 27-32 (Section 6). pdf file.
- Pages 33-38 (Section 7). pdf file.
- Pages 39-42 (Section 8). pdf file.
- Pages 43-46 (Section 9 - old version ). pdf file.
- Pages 43-46 (Section 9 - revised 25 April). pdf file. The revised version has a slightly simpler version of Lemma 9.4 and hence
a simpler proof of Theorem 9.5, as discussed in a lecture - otherwise, it is the same.
- Pages 47-48 (Section 10). pdf file.
Problem sheets
Solutions to problem sheets