# Coursebooks 2018-2019

## Probabilistic methods

Pach János

English

#### Remarque

Cours donné en alternance tous les 2 ans (donné en 2018-19)

#### Summary

We systematically explore the exciting fact that randomness (i.e., coin flipping) can be used profitably to construct various mathematical structures with unexpected and often paradoxical properties, and to efficiently solve otherwise hopelessly difficult computational tasks.

#### Content

• Linearity of expectation
• Applications in combinatorics and number theory
• Randomized algorithms (sorting, convex hull, linear programming)
• The second moment method
• Random graphs

#### Keywords

random variable, expected value, probabilistic method, random graph, coloring

#### Learning Prerequisites

##### Required courses

Probability theory

##### Recommended courses

Discrete Mathematics or Graph Theory

##### Important concepts to start the course

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

#### Learning Outcomes

By the end of the course, the student must be able to:
• Define and explain basic concepts in probability and discrete mathematics
• Define threshold functions, and analyze their asymptotic behavior
• 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 evolution of random graphs

#### 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

Exam written

#### Supervision

 Office hours Yes Assistants Yes

#### Resources

##### Bibliography

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

Stasys Jukna: Extremal Combinatorics (Springer)

### Reference week

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

Lecture
Exercise, TP
Project, other

### legend

• Autumn semester
• Winter sessions
• Spring semester
• Summer sessions
• Lecture in French
• Lecture in English
• Lecture in German