MATH-467 / 5 crédits

Enseignant: Marcus Adam Wade

Langue: Anglais


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

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)

Ressources en bibliothèque

Dans les plans d'études

  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Probabilistic methods in combinatorics
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines

Semaine de référence

 LuMaMeJeVe
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     

Vendredi, 13h - 15h: Cours MED21522

Vendredi, 15h - 17h: Exercice, TP MED21522