C8.4 Probabilistic Combinatorics (2024-25)
Main content blocks
- Lecturer: Profile: Oliver Riordan
Course information
General Prerequisites:
Part B Graph Theory and Part A Probability. C8.3 Combinatorics is not as essential prerequisite for this course, though it is a natural companion for it.
Course Term: Hilary
Course Lecture Information: 16 lectures
Course Weight: 1
Course Level: M
Assessment Type: Written Examination
Course Overview:
Probabilistic combinatorics is a very active field of mathematics, with connections to other areas such as computer science and statistical physics. Probabilistic methods are essential for the study of random discrete structures and for the analysis of algorithms, but they can also provide a powerful and beautiful approach for answering deterministic questions. The aim of this course is to introduce some fundamental probabilistic tools and present a few applications.
Learning Outcomes:
The student will have developed an appreciation of probabilistic methods in discrete mathematics.
Course Synopsis:
First-moment method, with applications to Ramsey numbers, and to graphs of high girth and high chromatic number.
Second-moment method, threshold functions for random graphs.
Lovász Local Lemma, with applications to two-colourings of hypergraphs, and to Ramsey numbers.
Chernoff bounds, concentration of measure, Janson's inequality.
Branching processes and the phase transition in random graphs.
Clique and chromatic numbers of random graphs.
Second-moment method, threshold functions for random graphs.
Lovász Local Lemma, with applications to two-colourings of hypergraphs, and to Ramsey numbers.
Chernoff bounds, concentration of measure, Janson's inequality.
Branching processes and the phase transition in random graphs.
Clique and chromatic numbers of random graphs.
Section outline
-
-
Lecture notes from 2019. No specific changes are planned this year, but it is possible that there may be minor changes, in which case updated notes will be uploaded.
-
-
Introductory problem sheet. Not for classes. Hints/solutions will be uploaded at the end of week 1.
-
Hints / solutions for the self-study sheet 0. Please try the questions before looking at the solutions!
-
Problem sheet for the first class. Based on material from weeks 1 and 2. Most questions accessible after week 1; Questions 6 and 7 use second moment ideas likely covered in Lecture 4 (but just the basics). Two versions, with and without solutions to question 1.
Version with hints for the MFoCS now added. -
Problem Sheet 2, based on lectures from weeks 3 + 4. Versions with and without solution to Q1. (Try it yourself before looking at the version with solution!)
Solutions to all questions (well, fairly detailed hints for Part C) have now been uploaded, since work for this sheet will not be marked. -
Problem sheet 3, based on material lectured in weeks 5 and 6.
Version with hint for MFoCS question will be added later. -
Problem sheet 4, for the final class. Three files; the problem sheet with and without solution to the section A question and (will be posted later) with solutions to all of sections A+B and hints for the optional/MFoCS questions. The problems should already be accessible after week 7 lectures.
-
-
-
Registration start: Monday, 13 January 2025, 12:00 PMRegistration end: Friday, 14 February 2025, 12:00 PM
-
Class Tutor's Comments Assignment
Class tutors will use this activity to provide overall feedback to students at the end of the course.
-