MATH-467 / 5 credits

Language: 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.

## Keywords

random variable, expected value, probabilistic method, random graph

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

## Bibliography

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

## In the programs

• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks
• Semester: Fall
• Exam form: Written (winter session)
• Subject examined: Probabilistic methods in combinatorics
• Lecture: 2 Hour(s) per week x 14 weeks
• Exercises: 2 Hour(s) per week x 14 weeks

## Reference week

 Mo Tu We Th Fr 8-9 9-10 10-11 11-12 12-13 13-14 MED21522 14-15 15-16 MED21522 16-17 17-18 18-19 19-20 20-21 21-22

Friday, 13h - 15h: Lecture MED21522

Friday, 15h - 17h: Exercise, TP MED21522