Tutorial: How to get answers that are certain using probability
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.100...
in particular pages 311-319, Probability makes counting (sometimes) easy
https://link.springer.com/chapter/10....
P. Erdős, On a problem in graph theory, Math. Gaz. 47 (1963), 220-223.
http://www.jstor.org/stable/3613396?o...
P. Erdős, L. Moser A problem on tournaments, Canad. Math. Bull. 7 (1964), 351-356
http://cms.math.ca/cmb/v7/cmb1964v07....
Outreach article (in French):
https://images.math.cnrs.fr/Probabili...
C code: https://github.com/nilsberglund-orlea...
https://www.idpoisson.fr/berglund/sof...
#probability #Erdos #tournament
