# Fiches de cours

## Probabilistic methods in combinatorics

English

#### Summary

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpected (and sometimes paradoxical) properties for which no other methods of construction are known.

#### Content

• Linearity of expectation
• The second moment method
• Local lemma
• Random graphs and matrices
• Applications in combinatorics and graph theory

#### Keywords

random variable, expected value, probabilistic method, random graph

#### Learning Prerequisites

##### Required courses

Probability theory

##### Recommended courses

• Discrete Mathematics or Graph Theory
• Linear Algebra

##### Important concepts to start the course

Graph, random variable, expectation, variance, binomial coefficients, asymptotics, eigenvalues

#### Learning Outcomes

By the end of the course, the student must be able to:
• Define and explain basic concepts in probability and discrete mathematics
• Prove explain, and apply the first and second moment methods
• Prove explain, and apply the Local Lemma
• Solve exercises, design randomized algorithms
• Describe and explain the method of interlacing polynomials

#### Transversal skills

• Summarize an article or a technical report.
• Demonstrate the capacity for critical thinking
• Assess progress against the plan, and adapt the plan as appropriate.

#### Teaching methods

Lectures and exercises

#### Expected student activities

Attending the lectures, solving the exercises, reading sections from the textbook

#### Assessment methods

Exam written

Dans le cas de l'art. 3 al. 5 du Règlement de section, l'enseignant décide de la forme de l'examen qu'il communique aux étudiants concernés.

#### Resources

##### Bibliography

Noga Alon-Joel Spencer: The Probabilistic Method (Wiley)

### Semaine de référence

LuMaMeJeVe
8-9
9-10
10-11
11-12
12-13
13-14    MAA330
14-15
15-16    MAA330
16-17
17-18
18-19
19-20
20-21
21-22

Cours
Exercice, TP
Projet, autre

### légende

• Semestre d'automne
• Session d'hiver
• Semestre de printemps
• Session d'été
• Cours en français
• Cours en anglais
• Cours en allemand