Random Discrete Structures

Department: 
MATH
Course Number: 
8803-WAR
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
Not regularly scheduled

Special topics  course on Random Discrete Structures, offered in Fall 2017 by Lutz Warnke.

Prerequisites: 

Math 6221 (Advanced Classical Probability Theory) or Math 7018 (Probabilistic Methods in Combinatorics) or Math 6241 (Probability I).

Course Text: 
- Alon-Spencer textbook on `The Probabilistic Method'
- Janson-Luczak-Rucinski textbook on `Random Graphs'
- Frieze-Karonski textbook on `Random Graphs'
- Steele textbook on `Probability Theory and Combinatorial Optimization'
- Boucheron-Lugosi-Massart textbook on `Concentration inequalities'
- Moore-Mertons textbook on `The Nature of Computation'
- Relevant research articles
Topic Outline: 
Outline of possible Topics:
- Subadditivity Methods: Basic examples, Interpolation method 
- Local Locasz Lemma: Moser-Tardos Algorithm
- Differential Equation Method: The two approaches of Wormald and Bohman, Self-correcting estimates via drift-analysis
- Concentration Inequalities: Talagrand, The entropy method
- Advanced Second Moment Method: Sharp thresholds, Weighted second moment method, Conditional second moment method
- Random Graphs: Random regular graphs, contiguity between various models, coupling of distributions