Instructor:  Prof. Linyuan Lu

Office: LC 403, 419A
Email: lu@math.sc.edu

Office hours: MW 1:00PM-2:00PM or by appointment.

Lecture time: MWF & 12:00PM- 12:50PM, LC 315

Credit Hours:  3

Prerequisite:  some background in graph theory and probability.

Reference textbook: Probabilistic methods (4rd edition), by Noga Alon, Joel H. Spencer, Wiley, 2016, ISBN: 978-1-119-06195-3.

Overview: The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdos, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error.

This method has now been applied to other areas of mathematics such as number theory, linear algebra, and real analysis, as well as in computer science (e.g. randomized rounding), and information theory.

Learning Outcomes: On successful completion of this course, graduate students will be able to:

1. Mastering the topics on the first moment methods, second moment methods, Lovasz Local Lemma, large deviation inequalities, FKG inequalities, Poisson paradigm, and random graphs.
2. Demonstrating the ability to use the probabilistic method to prove the existence of certain structures in graph theory, discrete math, number theory, etc.
3. Assess research papers and understand the proofs, which involves the probabilistic methods.

Subject Material:   The course will begin with a description of tools applied in probabilistic arguments, including basic techniques such as expectation, variance, martingales, and correlation inequalities. We will also examine selected topics where probabilistic techniques have been applied successfully such as random graphs, phase transition, discrepancy, circuit complexity, computational geometry, and derandomization of randomized algorithms.

Assessment:   The assessment consists of homeworks, an exam, and a final project. Homework will normally be assigned every other week. Although you can discuss the problems with others, you should write (type) up your homework solutions independently. A final project consists of reading a paper and presenting it into the class.

Grading: The breakup grades are homework 50%, exam 25%, and final project 25%. Your final grade is based on the percentage as follows.

Grading Scale

Lecture notes:

• Week 1: Linearity of Expectation (I)
• Week 2: Linearity of Expectation (II)
• Week 3: Alteration
• Week 4: The second moment method
• Week 5: Lovasz Local Lemma
• Week 6: Correlation Inequalities
• Week 7: Large Deviation Inequalities (I)
• Week 8: Large Deviation Inequalities (II)
• Week 9: Large Deviation Inequalities (III)
• Week 10: Poisson paradigm
• Week 11: Random graphs (I)
• Week 12: Random graphs (II)
• Week 13: Discrepancy
• Week 14: Entropy