Topics in Discrete Maths
Random Graphs and Thresholds
This is the last part of a course at Bristol University. (Links to the websites of Thomas Bloom and Robert Kurinczuk who took the first and second parts). A pdf of the content of each lecture, including exercises, will be uploaded after the lecture. I'll also maintain cumulative lecture notes and exercises. (Last updated 17th May).Office Hours : 2-3pm Thurs 19th May, 11-12pm Mon 7th March and 2-3pm Thu 17th March. These will be held in the second floor seminar room 2.1 of Howard House.
The homework is due by Fri 18th March 5pm. All questions are fair game excluding 3,4,6a which were covered in lectures. In particular - exercises 6b, 6c are still open and are good questions to attempt. Please either place your solutions in the box in the math dept or hand in to desk at Howard House. (Or at the office hour on Thu 17th March).
There is a practice exam question (now includes solutions) available for this part of the course.
|
■ Lecture 1: Introduction to random graphs and threshold functions. ■ Lecture 2: Threshold for cycles in random graphs. ■ Lecture 3: Threshold for a four vertex graph. Bollobas-Thomason Theorem. ■ Lecture 4: Introduction to Influence. Margulis-Russo Theorem. ■ Lecture 5: Maximum Influence of a monotone function. ▲ All Exercises: Recall exercises 3, 4, 6a were covered in the tutorial lecture. |
|
Possible ReadingThese go beyond the scope of this course.● Colin McDiarmid's Probabilistic Combinatorics course notes. p1-17. ● Oleg Pikhurko's slides on thresholds in random graphs. ● Lecture notes on noise sensitivity and percolation by Christophe Garban and Jeff Steif. |
 |