Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Math 7018 (Probability Methods in Combinatorics)
• Prerequisites: Undergrad Probability and Combinatorics or Consent of Instructor
Objective: Two-fold: To cover a few topics from classical probability theory and to develop an appreciation for the strength and beauty of the probabilistic techniques in combinatorics.
List of Topics: To be covered in an interlacing order of topics indicated by a * and a •
* Introduction: Sigma algebras, discrete and absolutely continuous distributions, Univariate r.v.s
* Expectation, Moment Generating Function and Properties of Characteristic Function
* Multivariate r.v.s: Joint Normal Distribution, Conditional Expectation, Chain rule for Variance, Entropy
* Convergence of Random Variables : Convergence in Probability, Almost Sure etc.
* Limit Laws: Weak and Strong Law of Large Numbers, The CLT, Berry-Esseen Theorem (Proofs are self-contained with the exception of assuming Dominated Convergence Theorem and Fubini’s Theorem; treatment as in Marc Berger’s book)
• Introduction to the probabilistic method: First moment method and variations
• Applications of Conditioning: Independence number of triangle-free graphs, RadhakrishanSrinivasan lower bound for Property B • The Second Moment Method: Examples from random graphs
• Lov´asz Local Lemma : Applications, variants and the algorithmic version
• Random Graphs: Connectivity, Threshold for appearance of balanced subgraphs, The Chromatic number, Existence of limits (for independence number, maxcut, max-coloring) in sparse random graphs
• Correlation Inequalities: FKG and the Ahlswede-Daykin Theorem, Janson’s inequality
• Martingale Inequalities: Azuma-Hoeffding inequality, Talagrand’s inequality
• Dependent Random Choice : Extremal numbers for bipartite graphs, The BalogSzemer´edi-Gowers theorem
• Entropy Techniques : Fractional subadditivity and submodularity, Shearer Lemma and applications to enumerative/additive combinatorics
• Miscellaneous: Some subset of Discrepancy of set systems, Sign Matrices, epsilon-nets, and VC-dimension
Suggested Textbooks:
* Probability and Random Processes, by Grimmett and Stirzaker, (3rd ed.) Oxford University Press, 2001.
* Introduction to Probability and Stochastic Processes, by Marc Berger, Springer-Verlag, 1992.
• The Probabilistic Method, by N. Alon and J. Spencer, Wiley (Fourth Edition, 2015).
Additional references:
! Random Graphs, S. Janson, T. Luczak, and A. Rucinski (Wiley-Interscience Series, 2000).
General grading policy : HWs 30% ; Two Tests 40% ; Final 30%
Test 1: Thursday, February 14th
Test 2: Thursday, April 4th
Final exam: Thursday, May 2, 11:20–2:10 pm
Homeworks will be assigned, collected and graded on a regular basis. You are strongly advised to (attempt to) solve all the homework problems. You are allowed to discuss your homework assignments with other students, but are required to write the solutions on your own. In other words, you are not allowed to copy another student’s solution.
Late submission of HWs is discouraged with a penalty of 20%.
Academic Dishonesty: All students are expected to comply with the Georgia Tech Honor Code. Any evidence of cheating or other violations of the Georgia Tech Honor Code will be submitted directly to the Dean of Students. The institute honor code is available at: http://www.policylibrary.gatech.edu/student-affairs/academic-honor-code