Tutorial: How to get answers that are certain using probability
Channel: Nils Berglund
Date: 28/05/2023

This talk is about the "probabilistic method", popularized by Paul Erdős, to show that certain types of mathematical objects exist. The method is explained in a particular example, having to do with organizing a tournament, and showing the existence of certain types of "undecidable" tournaments.

Introduction: 0:00
Paul Erdős: 0:34
Organizing a tournament: 3:24
Counting matches: 5:05
Counting outcomes: 12:27
Undecidable tournaments: 17:13
2-undecidable tournaments: 20:34
The probabilistic method: 25:54
The smallest 2-undecidable tournament: 37:27
k-undecidable tournaments: 40:56
Conclusion: 52:54

References:
M. Aigner and G. Ziegler,  Proofs from the Book (Springer, 2018)
https://link.springer.com/book/10.1007/978-3-662-57265-8 
in particular pages 311-319, Probability makes counting (sometimes) easy
https://link.springer.com/chapter/10.1007/978-3-662-57265-8_45
P. Erdős, On a problem in graph theory, Math. Gaz. 47 (1963), 220-223.
http://www.jstor.org/stable/3613396?origin=crossref&seq=1#page_scan_tab_contents
P. Erdős, L. Moser A problem on tournaments, Canad. Math. Bull. 7 (1964), 351-356
http://cms.math.ca/cmb/v7/cmb1964v07.0351-0356.pdf

Outreach article (in French):
https://images.math.cnrs.fr/Probabiliser.html?lang=fr

C code: https://github.com/nilsberglund-orleans/YouTube-simulations
https://www.idpoisson.fr/berglund/software.html

#probability #Erdos #tournament