# C8.4 Probabilistic Combinatorics - Material for the year 2020-2021

## Primary tabs

We have updated our Undergraduate exams guidance in preparation for the Trinity Term examinations.

Please see our new webpages dedicated to TT exams.

2020-2021
Lecturer(s):
Prof. Oliver Riordan
General Prerequisites:

B8.5 Graph Theory and A8: 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.00 unit(s)
Course Level:
M

### Assessment type:

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.