Instructor: Dr. Pawel Pralat, Department of Mathematics, Toronto Metropolitan University (TMU)
Email: pralat@ryerson.ca
Webpage: https://math.ryerson.ca/~pralat/
Registration Deadline: September 13th, 2022
Lecture Times: Wednesday | 6:00 - 9:00 PM (ET)
Office Hours: TBA (virtual, Zoom link will be provided)
Course Dates: September 7th - November 30th, 2022
Mid-Semester Break: October 10th - 14th, 2022
Registration Fee:PSU Students - Free | Other Students - $500 CAD
Prerequisites: N/A
Evaluation: The assessment of your performance in the course will be based on 10 assignments.

Discussion between students for general understanding of the material (or even about the assignment problems) is strongly encouraged. But all work to be submitted must reflect strictly individual effort. Plagiarism and cheating of any form will be dealt with according to university policy.

Capacity Limit: N/A

Format: Online (Zoom)

Course Material: Course information, course notes, handouts, announcements, assignments, solutions, etc., will be emailed directly to all students.

Textbooks: I will provide my notes (PDF file) so no textbook is required.

Course Description

The probabilistic method is a very powerful nonconstructive tool; it is used primarily in combinatorics, but has been successfully applied to many other areas of mathematics (such as number theory, linear algebra, and real analysis) as well as theoretical computer science (for example, randomized algorithms). This tool is used for proving the existence of an object having some given properties without actually finding it. A random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs. Both topics have experienced tremendous growth in the last few years, with an increasing number of applications in other areas of mathematics and computer science.

The course will focus on standard tools that can be immediately applied to solve some open problems in many areas of mathematics (both pure and applied). Of course, there are a number of highly nontrivial open problems in these areas, but there are also problems that can be solved by a graduate student equipped with the right collection of tools (especially problems that are multidisciplinary in nature). This was the main criterion during the selection process, so the topics covered are by no means exhaustive.

Course Outline

1. Non-constructive Proofs
2. Expectation
3. The First Moment Method
4. Variance and the Second Moment Method
5. Convergence of Moments Method
6. Concentration of Probability
7. Generating Functions and Branching Processes
8. Random d-regular Graphs
9. Martingales and the DE Method
10. Random Walks
11. Spectral Graph Theory (if there is enough time)
12. The Lovasz Local Lemma (if there is enough time)

Course Outline in PDF